# include <fstream>
# include <cstring>
# include <bitset>
# define DIM 1000010
# define DIV 78599
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bitset <DIM>f;
int d1[DIV],bz[100],t,q,k,k1,i,j,nd,ok,nr,r,sol;
long long d[DIV],x,a,b,s,p;
int main () {
    for(i=2;i<=DIM;i++){
            if(f[i]==0){
                d1[++k1]=i;
                for(j=2*i;j<=DIM;j+=i)
                    f[j]=1;
            }
        }
    fin>>t;
    for(q=1;q<=t;q++){
        sol=k=i=j=x=nd=ok=nr=r=a=b=s=0;
        fin>>a>>b;
        x=b;
        j=1;
        while(j<=k1&&x!=1){
            nr=0;
            while(x%d1[j]==0){
                x/=d1[j];
                nr++;
            }
            if(nr)
                d[++k]=d1[j];
            j++;
        }
        if(x>1)
            d[++k]=x;
        memset(bz,0,sizeof(bz));
        while(bz[0]==0){
            j=k;
            while(bz[j]==1)
                bz[j--]=0;
            bz[j]=1;
            p=1;
            nr=0;
            for(i=1;i<=k;i++)
                if(bz[i]==1){
                    p*=d[i];
                    nr++;
                }
            if(nr%2)
                s-=a/p;
            else
                s+=a/p;
        }
        fout<<s<<"\n";
    }
    return 0;
}