# include <fstream>
# define DIM 1000010
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int f[DIM],d[DIM/10],b[14],v[14],t,k,q,i,j,r,nr,sol;
long long n,m,p,x;
int main () {
    for(i=2;i*i<=DIM-5;i++)
        if(f[i]==0){
            d[++k]=i;
            for(j=2*i;j<=DIM-5;j+=i)
                f[j]=1;
        }
    for(;i<=DIM-5;i++)
        if(f[i]==0)
            d[++k]=i;
    fin>>t;
    for(r=1;r<=t;r++){
        fin>>n>>m;
        sol=0;
        x=m;
        q=0;
        for(i=1;i<=k&&x!=1&&d[i]*d[i]<=m;i++){
            nr=0;
            while(x%d[i]==0){
                x/=d[i];
                nr++;
            }
            if(nr)
                v[++q]=d[i];
        }
        if(x!=1)
            v[++q]=x;
        b[0]=0;
        while(b[0]==0){
            j=q;
            while(b[j]){
                b[j]=0;
                j--;
            }
            b[j]=1;
            p=1;
            nr=0;
            for(i=1;i<=q;i++)
                if(b[i]){
                    p*=v[i];
                    nr++;
                }
            if(nr%2==0)
                sol+=n/p;
            else
                sol-=n/p;
        }
        fout<<sol<<"\n";
    }
    return 0;
}