#include <bits/stdc++.h>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long A,B,prod,k,m,nr,j,ans,d,i,t,n,a[101],prim[100100];
bool ciur[1000010];

int main()
{
    for(d=2;d<=1000000;d++)
    {
        if(ciur[d]==0)
        {
            for(i=d*d;i<=1000000;i+=d)ciur[i]=1;
            t++;prim[t]=d;
        }
    }


    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>A>>B;

        k=1;m=0;ans=0;
        while(prim[k]*prim[k]<=B)
        {
            if(B%prim[k]==0)
            {
                m++;
                a[m]=prim[k];
                while(B%prim[k]==0)B/=prim[k];
            }
            k++;
        }
        if(B!=1)m++,a[m]=B;

        for(k=1;k<(1<<m);k++)
        {
            nr=0;prod=1;
            for(j=0;j<m;j++)
                if((k&(1<<j)))prod*=a[j+1],nr++;

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

        g<<A-ans<<'\n';
    }
    return 0;
}