#include<cstdio>
#include<bitset>
using namespace std;
int i,p[100005],cnt,q,lim,j,f[105],g,t;
long long a,b,nr,sol;
bitset<1000005> viz;
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    p[++q]=2; lim=1000000;
    for(i=3;i*i<=lim;i+=2)
        if(!viz[i])
        {
            p[++q]=i;
            for(j=i*i;j<=lim;j+=i*2) viz[j]=1;
        }
    for(;i<=lim;i+=2) if(!viz[i]) p[++q]=i;

    for(scanf("%d",&t);t;t--)
    {
        scanf("%lld%lld",&a,&b); g=-1;
        for(i=1;i<=q && 1LL*p[i]*p[i]<=b;i++)
            if(b%p[i]==0)
            {
                f[++g]=p[i];
                while(b%p[i]==0) b/=p[i];
            }
        if(b>1) f[++g]=b;

        g++; lim=1<<g; sol=0;
        for(i=1;i<lim;i++)
        {
            cnt=0; nr=1;
            for(j=0;j<g;j++)
                if((1<<j)&i) {cnt++; nr*=f[j];}
            if(cnt&1) sol+=a/nr;
            else sol-=a/nr;
        }
        printf("%lld\n",a-sol);
    }
    return 0;
}