#include <fstream>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long t, a, b, i, ciur[1000005], prim[35], dvprim[1000005], nr, nrt, j, p, q, ans, pr, k;
int main()
{
    for(i=2; i<=1000000; i++)
    {
        if(ciur[i]==0)
        {
            dvprim[++q]=i;
            for(j=2*i; j<=1000000; j+=i)
                ciur[j]=1;
        }
    }
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        p=dvprim[1];
        nrt=1;
        nr=0;
        ans=0;
        while(b>1 && nrt<=q)
        {
            if(b%p==0)
            {
                prim[nr++]=p;
                while(b%p==0)
                    b/=p;
            }
            p=dvprim[++nrt];
            if(p*p>b && b>1)
                p=b;
        }
        ans=0;
        for(i=1; i<(1<<nr); i++)
        {
            pr=1;
            k=0;
            for(int j=0; j<nr; j++)
                if(i&(1<<j))
                {
                    pr*=prim[j];
                    k++;
                }
            if(k)
            {
                if(k%2)
                    ans+=a/pr;
                else
                    ans-=a/pr;
            }
        }
        fout<<a-ans<<'\n';
    }
    return 0;
}