#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int nmax=1e6;
long long n,a,b,i,j,p,ciur[nmax+1],v[101],prim[nmax],k,rez,nr,nrc,s;
int main()
{
    for(i=2;i<=nmax;i++)
    {
        if(ciur[i]==0)
        {
            prim[++k]=i;
            for(j=i*2;j<=nmax;j+=i)
                ciur[j]=1;
        }
    }
    fin>>n;
    for(i=1;i<=n;i++)
    {
        k=0;
        fin>>a>>b;
        rez=0,nr=0,nrc=0;
        for(j=1;prim[j]*prim[j]<=b;j++)
        {
            if(b%prim[j]==0)
            {
                v[++k]=prim[j];
                while(b%prim[j]==0)
                    b/=prim[j];
            }
        }
        if(b>1)
            v[++k]=b;
                rez=a;
        for(j=1;j<(1LL<<k);j++)
        {
            nrc=0;
            s=1;
            for(p=0;p<k;p++)
            {
                if(((1LL<<p)&j)!=0)
                {
                    nrc++;
                    s=s*v[p+1];
                }
            }
            if(nrc%2==1)
            {
                rez=rez-a/s;
            }
            else
            {
                rez=rez+a/s;
            }
        }
        fout<<rez<<"\n";
    }
    return 0;
}