#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
using vl = vector<ll>;
const ll Nmax = 1e6+10, Lim = 1e6;
ll p = Lim-1;
char s[Lim];
void next()
{
    if(++p == Lim)
        fread(s,1,Lim,stdin), p=0;
}

void Get(ll &x)
{
    while(!isdigit(s[p]))next();
    for(x=0ll;isdigit(s[p]);next())
        x = x*10ll+(ll)(s[p]-'0');
}

bool prim[Nmax];
vl nrprime;

bool isprim(ll x)
{
    if(x<2) return false;
    if(x==2) return true;
    if(x%2==0) return false;
    for(int i=3;i*i<=x;i+=2) if(x%i==0)return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    memset(prim,true,sizeof prim);
    prim[0] = prim[1] = false;
    prim[2] = true;
    nrprime.push_back(2ll);
    for(ll i=3;i<Nmax;i+=2)
        if(prim[i])
    {
        nrprime.push_back(i);
        for(int j=i*3;j<Nmax;j+=2*i)
            prim[j] = false;
    }
    ll n;
    Get(n);
    vl div;
    for(int i=1;i<=n;i++)
    {
        ll a,b;
        Get(a);
        Get(b);
        div.clear();
        ll ans = a;
        for(auto c:nrprime)
        {
            //cout<<c<<" "<<b%c<<'\n';
            if(b%c == 0)
            {div.push_back(c);
            //cout<<c<<'\n';
            }
            while(b%c==0) b/=c;
            if(c*c>b) break;
        }
        if(isprim(b))
            {div.push_back(b);
            //cout<<b<<'\n';
            }
        ll sz = div.size();
        for(int k = 1; k < (1 << sz); ++k)
        {
        ll nr = 1;
        for(int j = 0; j < sz; ++j)
            if(k & (1 << j))nr *= div[j];

        if(__builtin_popcount(k) % 2 == 1)ans -= a / nr;
        else ans += a / nr;
        }
        div.clear();
        printf("%lld\n",ans);
    }
    return 0;
}