#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define ull unsigned long long int
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
vector<ull> primes;
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;
    };
};
int * primeDivisors(ull n, ull &nr)//O(sqrt(n)) complexitate
{
    int * prime = new int[100];
    nr = 0;
    for(ull i = 2 ; n > 1; i++)//we go just to sqrt(n) and while we have prime divisors to search
        if(n%i == 0)
        {
            while(n%i == 0)
                n/=i;
            prime[++nr] = i;
        }
    return prime;
}
void findPrimes()
{
    int dim = 1000000;
    bitset<1000003> v;
    primes.push_back(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.push_back(i);
}
int* primeDivisors2(ull n, ull &nr)
{
    int *prime;
    vector<ull> primeDiv;
    nr = 0;
    for(auto it = primes.begin() ; it!= primes.end() &&  *it <= n; it++)
        if(n %(*it) == 0)
        {
            nr++;
            primeDiv.push_back(*it);
        }
    prime = new int[nr+2];
    int i= 0;
    for(auto p:primeDiv)
        prime[++i] = p;
    if(nr == 0)
        prime[1] = n;
    return prime;
}
ull solve2(ull a, ull b)
{
    ull nr ;
    int * d = primeDivisors2(b,nr);
    ull sum = 0;
    ull prod = 1;
    for(int i = 1 ; i <= nr ; i ++)
    {
        sum += 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;
    }
    return a - sum;

}
ull gcd(ull a , ull b);
ull solve1(ull a, ull b);
int main()
{
    findPrimes();
    ull m,a,b;
    in >> m;
    while(m--)
    {
        in >> a >> b;
        out << solve2(a,b) << '\n';
    }
    return 0;
}
/*ull solve1(ull a, ull b)
{
    ull nr = 0;
    for(ull i = 1 ; i <= a ; i ++)
        if(gcd(i,b) == 1)
            nr++;
    return nr;
}*/
ull gcd(ull a , ull b)
{
    ull r;
    while(b)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}