#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
#define ull  unsigned long long int
ifstream in("pinex.in");
ofstream out("pinex.out");
ull primes[100000];
int nrprimes = 0;
struct Combinare
{
    int n,p;
    bool as,ev;
    Combinare(int a, int b):n(a),p(b){};
    void valid(int k, int *v, bool &ev)
    {
        int i;
        ev = true;
        if( k > 0 && v[k]<=v[k-1])
            ev = false;
    };
    void init( int k, int  *v)
    {
        v[k] = 0;
    };
    void suc(int k, int v[], bool &as)
    {
        if( v[k]< n-p+k+1)
        {
            v[k]++;
            as = true;
        }
        else
            as = false;

    };
    int* vectorSolutie(int k, int v[])
    {
        int * comb = new int[k+1];
        for(int i = 0 ; i < p; i ++)
            comb[i] = v[i] ;
        return comb;
    };
    bool solutie(int k)
    {
        if(k == p-1)
            return true;
        return false;
    };
    int ** Cnp(int & nrofCnp)
    {
        nrofCnp = 0;
        int ** combinari = new int*[(1<< n)+4];

        int v[n];
        int k = 0;
        init(k,v);
        while( k>-1 )
        {
            do
            {
                suc(k,v,as);

                if(as)
                    valid(k,v,ev);
            }
            while( as  && !(as && ev));
            if (as)
                if(solutie(k))
                    combinari[++nrofCnp] = vectorSolutie(k,v);
                else
                {
                    k++;
                    init(k,v);
                }
            else
                k--;
        }
        return combinari;
    };
};
void findPrimes()
{
    const int dim = 1000001;
    bitset<dim+5> v;
    primes[++nrprimes] = 2;
    for(int i = 3 ; i *i < dim ; i+= 2)
        if (v[i] == 0)
        {

            for(int  j = i*i ;  j < dim ; j += 2*i)
                v[j] = 1;
        }
    for(int i = 3 ;  i < dim ; i +=2)
        if(v[i] == 0)
            primes[++nrprimes] = i;

}
ull* primeDivisors2(ull n, ull &nr)
{
    ull *prime = new ull[100];
    nr = 0;
    ull i = 0;
    while ( n > 1 )
    {
        i++;
        if(n % primes[i] == 0)
        {
            prime[++nr] = primes[i];
             while(n%primes[i] == 0)
                n/=primes[i];
        }
         if(primes[i]*primes[i] > n && n>1)
        {
            prime[++nr] = n;
            n = 1;
        }
    }
    return prime;
}
ull solve2(ull a, ull b)
{
    ull nr ;
    ull * d = primeDivisors2(b,nr);
    ull sum = 0;
    ull prod = 1;
    for(int i = 1 ; i <= nr ; i ++)
    {
        sum += floor(a/d[i]);
        prod *= d[i];
    }
    if(nr>1)
        if(nr%2 ==0 )
            sum -= a/prod;
        else
            sum += a/prod;
    for(int i = 2 ; i < nr ; i ++)
    {
        Combinare c(nr,i);
        int com;
        int ** sol = c.Cnp(com);
        for(int j = 1 ; j <= com ; j++)
        {
            prod = 1;
            for(int k = 0 ; k < i ; k++)
                prod *= d[sol[j][k]];
            sum += ((a/prod) * ((i % 2 ==0)?-1:1));
            delete []sol[j];
        }
        delete []sol;
    }

    delete []d;
    return a - sum;

}
int main()
{
    findPrimes();
    ull m,a,b;
    in >> m;
    while(m--)
    {
        in >> a >> b;
        out << solve2(a,b) << '\n';
    }
    return 0;
}