#include<cstdio>
long long m,ca,pri[100001],a,b,j,k,s,cj,prod,var,cati,d,cate,v[80010],ciur[1000001],lalala,ioi=1;
int main(){
    long long i;
      FILE *in=fopen("pinex.in","r"), *out=fopen("pinex.out","w");
    fscanf(in,"%lld",&m);
    d=2;
    ca=0;
    lalala=1000000;
    while(d*d<lalala){
        for(i=2;i*d<=lalala;i++)
            ciur[i*d]=1;
        d++;
        while(ciur[d]==1)
            d++;
    }
    for(i=2;i<=lalala;i++)
        if(ciur[i]==0)
        {
            ca++;
            pri[ca]=i;
        }
    for(k=1;k<=m;k++){
        fscanf(in,"%lld%lld",&a,&b);
        //descompun in factori primi b
        cate=0;
        ca=1;
        while(b>1){
            if(b%pri[ca]==0){
               cate++;
               v[cate]=pri[ca];
                while(b%pri[ca]==0)
                     b/=pri[ca];
             }
            if((pri[ca]+1)*(pri[ca]+1)>b&&b>1){
                cate++;
                v[cate]=b;
                b=1;
            }
            else{
                ca++;
            }
        }
        s=0;
        var=ioi<<cate;
        for(j=1;j<var;j++){
            cj=j;
            prod=1;
            cati=0;
            for(i=0;i<=63;i++){
                if(cj&(ioi<<i)){
                    cati++;
                    prod*=v[i+1];
                }
            }
            if(cati%2==1)
                s+=(a/prod);
            else
                s-=(a/prod);
        }
    fprintf(out,"%lld\n",a-s);
    }
return 0;
}