#include<cstdio>
long long a,b,m,i,j,v[1000010],x[100010],y[100010],nr,nmax,nrs,s,q,k;
FILE *f,*g;
int main(){
    f=fopen("pinex.in","r");
    g=fopen("pinex.out","w");
    fscanf(f,"%d",&m);
    for(i=2;i<=1000010;i++){
        if(v[i]==0){
            x[++nr]=i;
            for(j=i+i;j<=1000010;j+=i){
                v[j]=1;
            }
        }
    }
    while(m!=0){
        fscanf(f,"%lld%lld",&a,&b);
        k=0;
        for(i=1;i<=nr&&x[i]<=b/x[i];i++){
            if(b%x[i]==0){
                y[++k]=x[i];
                while(b%x[i]==0)
                    b/=x[i];
            }
        }
        if(b!=1)
            y[++k]=b;
        nmax=(1LL<<k)-1;
        nrs=a;
        for(i=1;i<=nmax;i++){
            s=1;
            q=0;
            for(j=0;j<k;j++){
                if(((i>>j)&1LL)==1LL){
                    q++;
                    s*=y[j+1];
                }
            }
            if(q%2==0)
                nrs+=a/s;
            else
                nrs-=a/s;
        }
        fprintf(g,"%lld\n",nrs);

        m--;
    }






    fclose(f);
    fclose(g);
    return 0;
}