#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[100011];
int prim[100011];

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);

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

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

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

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