#include <bits/stdc++.h>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
typedef long long ll;
const ll lim=1e6+4;
vector<ll> primes;
vector<ll> used;
bool ok[lim];
ll tst,a,b;
int main()
{
    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;
    }
    in>>tst;
    while(tst--)
    {
        in>>a>>b;
        for(ll i=0;i<primes.size() and primes[i]*primes[i]<=b;++i)
        if(b%primes[i]==0)
        {
            used.push_back(primes[i]);
            while(b%primes[i]==0)
                b/=primes[i];
        }
        ll ans=0;
        if(b>1) used.push_back(b);
        ll nr=used.size();
        for(ll mask=0;mask<(1LL<<nr);++mask)
        {
            ll app=0,prod=1;
            for(ll i=0;i<nr;++i)
            if(mask&(1LL<<i)) ++app,
                prod*=used[i];
            if(app%2==0) ans+=a/prod;
            else ans-=a/prod;
        }
        out<<ans<<'\n';
        used.clear();
    }
    return 0;
}