#include<stdio.h>
long long m,a,b,j,k,s,cj,prod,var,cati,d,cate,v[80010],ciur[1000001],lalala,ioi=1;
int main(){
    long long i;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%lld",&m);
    d=2;
    lalala=1000000;
    while(d*d<1000000){
        for(i=2;i*d<=lalala;i++)
            ciur[i*d]=1;
        d++;
        while(ciur[d]==1)
            d++;
    }

    for(k=1;k<=m;k++){
        scanf("%lld%lld",&a,&b);
        //descompun in factori primi b
        d=2;
        cate=0;
        while(b!=1){
            if(b%d==0){
               cate++;
               v[cate]=d;
                while(b%d==0)
                     b/=d;
             }
            if((d+1)*(d+1)>b&&b>1){
                cate++;
                v[cate]=b;
                b=1;
            }
            else{
            d++;
            while(ciur[d]==1&&d<1000001)
                d++;
            }
            }
        s=0;
        var=1<<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);
        }
    printf("%lld\n",a-s);
    }
return 0;
}