#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

int E[999999], P[99999], Ps=0;

int main(){
    int M,i,j,k,Ds;
    unsigned long long A,B,D[30],x,c,s;
    E[0]=E[1]=1;
    for(i=2; i<999; i++)
        if(!E[i])
            for(j=i*i; j<999999; j+=i)
                E[j]=1;
    for(i=2; i<999999; i++)
        if(!E[i])
            P[Ps++]=i;
    fin>>M;
    while(M--){
        fin>>A>>B;
        Ds=0;
        for(i=0; i<Ps; i++)
            if(B%P[i]==0){
                D[Ds++]=P[i];
                while(B%P[i]==0)
                    B/=P[i];
            }
        if(B!=1)
            D[Ds++]=B;
        s=A;
        for(i=1; i<(1<<Ds); i++){
            x=1; c=0; j=i;
            for(k=0; k<Ds; k++){
                if(j%2){
                    x*=D[k];
                    c++;
                }
                j/=2;
            }
            if(c%2) s-=A/x;
            else s+=A/x;
        }
        fout<<s<<'\n';
    }
    return 0;
}