#include<bits/stdc++.h>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int T,A,B,l,fp[1000001];
long long nr;
void descfactpr(int x){
    int n=x,f=2;
    l=0;
    while(f*f<=n){
        if(x%f==0){
            fp[++l]=f;
            while(x%f==0)x/=f;
        }
        if(f==2)++f;
        else f+=2;
    }
    if(x>1)fp[++l]=x;
}
int main()
{
    f>>T;
    while(T--){
        f>>A>>B;
        descfactpr(B);
        if(l==1)g<<A-A/fp[1]<<'\n';
        else if(l==2)g<<A-(A/fp[1]+A/fp[2]-A/(fp[1]*fp[2]))<<'\n';
        else{
            nr=1;
            for(int i=1;i<=l;++i)nr+=A/fp[i];
            for(int i=1;i<(1<<l);++i){
                int num=0;
                long long p=1;
                for(int j=0;j<=l;++j)
                    if(i&(1<<(j-1)))
                        ++num,p*=fp[j];
                if(num!=1&&num!=l)nr-=A/p;
            }
            g<<A-nr<<'\n';
        }
    }
    return 0;
}