#include <stdio.h>
#define lim 1000000
bool ciur[lim+5];
int v[lim/3],d[lim/3];
void ciuruire(){
    int i,j;
    for(i=2;i*i<lim;i++)
        if(ciur[i]==false)
            for(j=i*i;j<lim;j+=i)
                ciur[j]=true;
    ciur[0]=true;
    ciur[1]=true;
    for(i=2;i<=lim;i++)
        if(ciur[i]==false){
            v[0]++;
            v[v[0]]=i;
        }
}
int main(){
    FILE *fin,*fout;
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    long long a,b,c,i,j,k,n,nr,nrd,s,val;
    ciuruire();
    fscanf(fin,"%lld",&n);
    for(k=1;k<=n;k++){
        fscanf(fin,"%lld%lld",&a,&b);
        c=b;
        nrd=0;
        for(i=1;i<=v[0]&&v[i]*v[i]<=b;i++)
            if(b%v[i]==0){
                d[nrd]=v[i];
                nrd++;
                c=c/v[i];
            }
        if(c!=1){
            d[nrd]=c;
            nrd++;
        }
        s=0;
        for(i=0;i<(1<<nrd);i++){
            val=1;
            nr=0;
            for(j=0;j<nrd;j++)
                if(i&(1<<j)){
                    val=val*(long long)d[j];
                    nr++;
                }
            if(nr%2==0)
                s+=a/val;
            else
                s-=a/val;
        }
        fprintf(fout,"%lld\n",s);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}