#include <fstream>
std::ifstream cin("pinex.in");
std::ofstream cout("pinex.out");
#define ll long long
#define maxn 1000005
ll m,a,b,facts[80000];
bool ciur[maxn];

void preCalcPrimes(){
    for(int i=4;i<maxn;i+=2)
        ciur[i]=1;
    facts[++facts[0]]=2;
    for(int i=3;i<maxn;i+=2){
        if(!ciur[i]){
            facts[++facts[0]]=i;
            for(int j=i+i+i;j<maxn;j+=(i<<1))
                ciur[j]=1;
        }
    }
}


ll solve(ll a,ll b){
    ll prod=1,sol=a;
    int t=0,nr,nrprim[50],cnt=0;
    while(b>1){
        ++cnt;
        if(b%facts[cnt]==0){
            nrprim[++t]=facts[cnt];
            while(b%facts[cnt]==0)
                b/=facts[cnt];
        }
        if(facts[cnt]*facts[cnt]>b&&b>1){
            nrprim[++t]=b;
            b=1; break;
        }
    }
    for(int i=1;i<(1<<t);i++){
        nr=0,prod=1;
        for(int j=0;j<t;j++)
            if((1<<j)&i){
                prod=1LL*prod*nrprim[j+1];
                nr++;
            }
        if(nr%2)nr=-1;
        else nr=1;
        sol+=(a/prod*nr);
    }
    return sol;
}


int main()
{
    cin>>m;
    preCalcPrimes();
    for(;m--;){
        cin>>a>>b;
        cout<<solve(a,b)<<'\n';
    }
    return 0;
}