#include <fstream>
#include <cmath>
#include <vector>
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];

vector<int> prim,nrprim;

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

void track(int poz,long long prod,int nr){
    if(poz>=prim.size()){
        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=0;i<=nrprim.size() && nrprim[i]<=B && B!=1;i++){
            if(!(B%nrprim[i])){
                prim.push_back(nrprim[i]);
                while(B%nrprim[i]==0)
                    B/=nrprim[i];
            }
        }
        if(B!=1)
            prim.push_back(B);
        track(0,1,0);
        g<<sol<<"\n";
        prim.clear();
    }

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