#include<fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long T,a,b,nro,i,j,k,t,ok,E,P,s,bb;
long long f[2000010];
long long e[1000000],poz[1000000],p[1000000];

void ciur(){
    for(i=2;i<1000010;i++){
        if(f[i]==0){
            p[++k]=i;
            for(j=i+i;j<1000010;j+=i)
                f[j]=1;
        }
    }
    return ;
}

void Code(){
    for(t=1;t<=T;t++){
        fin>>a>>b;
        s=0;
        bb = b;
        E = 0;
        for(i=1;p[i] * 1LL * p[i] <= bb && b != 1;i++){
            ok=0;
            while(b%p[i]==0){
                b/=p[i];
                ok=1;
            }
            if(ok==1)
                e[++E]=p[i];
        }
        if(b != 1)
            e[++E]= b;

        nro=0;
        for(i=0;i<=E;i++)
            poz[i]=0;

        while(poz[0] == 0){
            i=E;
            while(poz[i]==1){
                poz[i--]=0;
                nro --;
            }
            poz[i]=1;
            nro++;
            if (i==0)
                break;
            P=1;
            for(i=1;i<=E;i++){
                if(poz[i]==1){
                    P*=e[i];
                }
            }
            if(nro%2==1)
                s=s+a/P;
            else
                s=s-a/P;
        }
        fout<<a-s << "\n";
    }
    return ;
}

int main(){
    fin>>T;
    ciur();
    Code();
    return 0;
}