#include <fstream>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");

const int nmax = 1000000;
int n,nr_fprimi;
int primii[79000];
long long factori[15], a, b, rasp;
bool ciur[nmax];

int fact()
{
    int p = 0 ;
    for(int i = 2 ; i <nmax ; i++)
    {
        if(ciur[i]==0)
        {
            for(int j = i + i ; j<nmax; j += i)
                ciur[j] = true;
            primii[p] = i;
            p++;
        }
    }

    return p;
}
 
int descomp(long long b)
{
    int nr_fac = 0;
    for(int i = 0 ; i < nr_fprimi  && b != 1; i++)
        if( b % primii[i] == 0)
        {
            while(b % primii[i] == 0)
                b /= primii[i];
            factori[nr_fac++]= primii[i];
        }
    if( b != 1)
        factori[nr_fac++] = b;
    return nr_fac;
}
 
long long sume(int nr)
{
    long long suma = 0;
    for(int x = 1 ; x < ( 1 << nr) ; x++)
    {
        int nr1 = 0;
        long long p = 1;
        for(int j = 0 ; j < nr ; j ++)
            if((x & (1 << j)) != 0 )
            {
                p *= factori[j];
                nr1++;
            }
        if (nr1 % 2 == 0)
            suma -=a / p;
        else
            suma += a / p;
    }
    return suma;
}

int main()
{
	int player_unu=0;
    in>>n;

    nr_fprimi = fact();
    for(int i = 0 ; i<n; i++)
    {
        in>>a>>b;

        rasp = a - sume(descomp(b));
        out<<rasp<<'\n';
    }

    return player_unu;
}