#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const long long e6 = 1e6;

bool ciur[e6+5];
int primes[e6+5];
long long crp[e6+5];

int main()
{
    long long m,a,b;
    fin >> m;

    long long crt = 0;
    for(long long i=2 ; i<=e6 ; ++i)
    {
        if(!ciur[i])
        {
            primes[++crt]=i;

            for(long long j=2*i ; j<=e6 ; j+=i)
            {
                ciur[j] = true;
            }
        }
    }

    while(m--)
    {
        fin >> a >> b;

        long long cr = 0;
        for(long long i=1 ; i<=crt ; ++i)
        {
            if(b%primes[i]==0)
            {
                crp[++cr]=primes[i];
            }
            while(!(b%primes[i]))
                b/=primes[i];
            if(b==1)
                break;
        }
        if(!cr)
            crp[++cr]=b;

        long long ans = 0;

        for(long long i=0 ; i<(1<<(cr)) ; ++i)
        {
            long long oc = 0;
            long long nn = 1;
            for(long long j=1 ; j<=cr ; ++j)
            {
                if((i>>(j-1))&1)
                {
                    oc++;
                    nn *= crp[j];
                }
            }

            if(oc%2)
                ans -= a/nn;
            else
                ans += a/nn;
        }
        fout << ans << '\n';
    }

    return 0;
}