#include <bits/stdc++.h>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bool a[1000010];
long long d,t,i,n,k,A,b,j,m,nr,prod,S,sol[1001],prim[1000010];
int main()
{
    for(d=2;d*d<=1000000;d++)
    if(a[d]==0)
    {
        t++;
        prim[t]=d;
        for(i=d*d;i<=1000000;i=i+d)
            a[i]=1;
    }

    for(i=1000;i<=1000000;i++)
        if(a[i]==0){t++;prim[t]=i;}

    f>>n;
    for(k=1;k<=n;k++)
    {
        f>>A>>b;
        j=1;m=0;S=0;
        while(prim[j]*prim[j]<=b)
        {
            if(b%prim[j]==0)
            {
                while(b%prim[j]==0)
                    b=b/prim[j];
                m++;
                sol[m]=prim[j];
            }
            j++;
        }

        if(b!=1){m++;sol[m]=b;}




        for(i=1;i<(1<<m);i++)
        {
            nr=0;
            prod=1;
            for(j=0;j<m;j++)
                if((i&(1<<j)))
                {
                    nr++;
                    prod=prod*sol[j+1];
                }

            if(nr%2==1)S=S+A/prod;
            else S=S-A/prod;
        }

        g<<A-S<<'\n';



    }

    return 0;
}