#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long C[1000004],v[1000004],a[1000004],w[104],A,B,q,k,n;
int main()
{
    fin>>q;
    for(long long i=2;i*i<=1000000;i++)
        if(C[i]==0)
        {
            v[++k]=i;
            for(long long j=1;j*i<=1000000;j++)
                C[i*j]=1;
        }
    for(;q>0;q--)
    {
        fin>>A>>B;
        n=0;
        for(long long i=1;v[i]*v[i]<=k && i<=k;i++)
        {
            if(B%v[i]==0)
            {
                a[++n]=v[i];
                while(B%v[i]==0)
                    B/=v[i];
            }
        }
        if(B>1)
            a[++n]=B;
        long long s=0;
        for(long long i=0;i<=n;i++)
            w[i]=0;
        while(!w[0])
        {
            long long j=n;
            for(;w[j]==1;j--)
                w[j]=0;
            w[j]=1;
            if(w[0]==1)
                break;
            long long nr=0,s1=1;
            for(long long i=1;i<=n;i++)
            {
                if(w[i]==true)
                {
                    nr++;
                    s1*=a[i];
                }
            }
            if(nr%2==1)
                s+=A/s1;
            else
                s-=A/s1;
        }
        if(s<0)
            s*=(-1);
        fout<<A-s<<"\n";
    }
    return 0;
}