#include <fstream>
#include <cmath>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int T,A,B,k;
long long vr=0,sol=0,q=1;
bool viz[1000011];
int nrprim[1000011];
int prim[1000011];

void ciur(){
    for(register int i=2;i<1000000;i++){
        if(!viz[i]){
            nrprim[++nrprim[0]]=i;
            for(register int j=i+i;j<=1000000;j+=i)
                viz[j]=true;
        }
    }
}

void track(int poz,long long prod,int nr){
    if(poz>k){
        sol+=(nr%2==0?1:-1)*(A/prod);
        return;
    }
    track(poz+1,prod,nr);

    nr++;
    prod*=prim[poz];
    track(poz+1,prod,nr);
    prod/=prim[poz];
    nr--;
}

int main(void){
    register int i,j,t,fin,st;

    ciur();
    f>>T;
    for(;T>0;T--){
        f>>A>>B;
        if(B==1){
            g<<A<<"\n";
            continue;
        }
        if(A==1){
            g<<"1\n";
            continue;
        }
        k=0,sol=0;
        int valmax=floor(sqrt(B));
        for(i=1;i<=nrprim[0] && nrprim[i]<=valmax && B!=1;i++){
            if(!(B%nrprim[i])){
                prim[++k]=nrprim[i];
                while(B%nrprim[i]==0)
                    B/=nrprim[i];
            }
        }
        if(B!=1){
            prim[++k]=B;
        }
        track(1,1,0);
        g<<sol<<"\n";
    }

    f.close();
    g.close();
    return 0;
}