#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const ll NMAX = 100005;
ll prim[NMAX],a[105],rasp,T,A,B,cnt;
bool ver[10*NMAX];
void ciur(){
    for(ll i=2;i<=1000005;i++){
        if(ver[i]==false){
            prim[++cnt]=i;
            for(ll j=1LL*i*i;j<1000005;j+=i)
                ver[j]=true;
        }
    }
}
int main()
{
    ciur();
    fin >> T;
    for(ll t=1;t<=T;t++){
        fin >> A >> B;
        ll nr=0,i=1;
        while(B>1 and 1LL*prim[i]*prim[i]<=B){
            if(B%prim[i]==0){
                a[++nr]=prim[i];
                while(B%prim[i]==0)
                    B/=prim[i];
            }
            i++;
        }
        if(B>1) a[++nr]=B;
        rasp=A;
        for(ll i=1;i<(1LL<<nr);i++){
            ll k=0,p=1;
            for(ll j=0;j<nr;j++){
                if(i&(1LL<<j)){
                    k++;
                    p=1LL*p*a[j+1];
                }
            }
            if(k%2==0) rasp=rasp+A/p;
            else       rasp=rasp-A/p;
        }
        fout << rasp << '\n';
    }
    return 0;
}