#include<stdio.h>
int n,np,p[1000013],nd,nr;
long long a,b,x,y,z,d[100],q,i,j;
bool k[1000013];
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&n);
	for(i=2;i<=1000000;++i)k[i]=1;
    for(i=2;i*i<=1000000;++i)
        if(k[i]) for(j=i;i*j<=1000000;++j)k[i*j]=0;
    for(i=2;i<=1000000;++i)if(k[i])p[np++]=i;
    for(int w=0;w<n;++w)
    {
        scanf("%lld%lld",&a,&b);
        i=0;
        nd=0;
        for(i=0;i<np && b!=1;++i)
            if(b%p[i]==0)
                {
                    while(b%p[i]==0)b/=p[i];
                    d[nd++]=p[i];
                }
        if(b!=1)d[nd++]=b;
        q=(long long)1<<nd;
        z=0;
        for(i=1;i<q;++i)
        {
            x=1;
            nr=0;
            for(j=0;j<nd;++j)
                if(i & ((long long)1<<j)) x*=d[j],++nr;
            if(nr%2==0)x=-x;
            z+=(a/x);
        }
        printf("%lld\n",a-z);
    }
    return 0;
}