#include <fstream>

using namespace std;

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

bool v[10000005];
bool a[10000005];
int q,i,j,k,k1,y,n,x,c,total,p[10000005],p1[10000005];

int main()
{
    fin >> q;
    for (i=2;i<=1000005;i++)
    {
        if (v[i]==0)
        {
            k++;
            p[k]=i;
            for (j=2*i;j<=1000005;j+=i) v[j]=1;
        }
    }
    for (y=1;y<=q;y++)
    {
        fin >> n >> x;
        k1=0;
        for (i=1;p[i]*p[i]<=x && i<=k && x!=1;i++) if (x%p[i]==0)
        {
            k1++;
            p1[k1]=p[i];
            while (x%p[i]==0) x/=p[i];
        }
        if (x!=1)
        {
            k1++;
            p1[k1]=x;
        }
        total=0;
        for (i=1;i<=k1+2;i++) a[i]=0;
        while(a[k1+1]==0)
        {
            i=1;
            while(a[i]==1) a[i++]=0;
            a[i]=1;
            if(i==k1+1) break;
            c=0;
            j=1;
            for(i=1;i<=k1;i++) if(a[i])
            {
                j*=p1[i];
                c++;
            }
            if(c%2==1) total+=n/j;
            else total-=n/j;
        }
        fout << n-total << "\n";
    }

    return 0;
}