#include <bits/stdc++.h>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
typedef long long ll;
const ll lim=1e6+3;
vector<ll> primes;
bool ok[lim];
void ciur()
{
    for(ll i=2;i<lim;++i)
    if(!ok[i])
    {
        primes.push_back(i);
        for(ll j=2*i;j<lim;j+=i)
            ok[j]=true;
    }
}
vector<ll> dv;
ll q,a,b;
int main()
{
    ciur();
    in>>q;
    while(q--)
    {
        in>>a>>b;
        ll ans=0;
        dv.clear();
        for(ll i=0;i<primes.size() and primes[i]*primes[i]<=b;++i)
        if(b%primes[i]==0)
        {
            dv.push_back(primes[i]);
            while(b%primes[i]==0)
                b/=primes[i];
        }
        if(b>1) dv.push_back(b);
        for(ll k=1;k<(1<<((ll)dv.size()));++k)
        {
            ll mask=k,prod=1,cnt=0;
            for(ll i=0;i<dv.size();++i,mask>>=1)
            if(mask&1) prod*=dv[i],++cnt;
            if(cnt&1) ans+=(a/prod);
            else ans-=(a/prod);
        }
        out<<a-ans<<'\n';
    }
    return 0;
}