#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
using vl = vector<ll>;
const ll Nmax = 1e6+1, Lim = 1e5;
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;
ll dp[Nmax]; /// dp[i] = nr. de elem divizibile cu i
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;
    for(ll i=2;i<Nmax;i++)
        if(prim[i])
    {
        nrprime.push_back(i);
        for(int j=i*2;j<Nmax;j+=i)
            prim[j] = false;
    }
    ll n;
    Get(n);
    for(int i=1;i<=n;i++)
    {
        ll a,b;
        Get(a);
        Get(b);
        vl div;
        ll ans = a;
        for(auto c:nrprime)
        {
            if(c > b) break;
            if(b%c == 0)
            {
                div.push_back(c);
                dp[c] = a/c;
            }
        }
        int 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;
}