# include <fstream>
# include <cmath>
# include <cstring>
# define DIM 1000010
# define DIV 78599
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool f[DIM],bz[100];
int d1[DIV],t,q,k,k1,i,j,nd,ok,nr,r,sol;
long long d[DIV],x,a,b,s,p;
int main () {
    fin>>t;
    for(q=1;q<=t;q++){
        sol=k=k1=i=j=x=nd=ok=nr=r=a=b=s=0;
        fin>>a>>b;
        for(i=2;i*i<=b;i++){
            if(f[i]==0){
                d1[++k1]=i;
                for(j=2*i;j*j<=b;j+=i)
                    f[j]=1;
            }
        }
        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;
}