# include <bits/stdc++.h>
# define ll long long
using namespace std;
ifstream fi("pinex.in");
ofstream fo("pinex.out");
const int nmax = 1e6 + 55;
bitset < nmax > b;
vector < int > prim;
vector < int > fact;
int k;
ll ans(ll a,ll n)
{
    int d = -1;
    fact.clear();
    while (n > 1)
    {
        ++d;
        if (!(n%prim[d]))
        {
            fact.push_back(prim[d]);
            while (!(n%prim[d])) n /= prim[d];
        }
        if (prim[d] > sqrt(n) && n != 1)
        {
            fact.push_back(n);n = 1;
        }
    }
    k = fact.size();
    int l = 1 << k;
    ll sol = 0;
    for (ll p = 1;p < l;++p)
    {
        ll nr = 0;
        ll pr = 1;
        for (int i = 0;i < k;++i) if ((1LL << i)&p) ++nr,pr *= fact[i];
        if (nr&1) nr = 1;else nr = -1;
        sol += a / (pr*nr);
    }
    return a - sol;
}
int main(void)
{
    ll x,y;
    for (int i = 3;i <= 1e6;i += 2) b[i] = 1;
    prim.push_back(2);
    for (int i = 3;i <= 1e3;i += 2)
        if (b[i])
        {
            prim.push_back(i);
            for (int j = i*i;j <= 1e6;j += i) b[j] = 0;
        }
    for (int i = 1e3+1;i <= 1e6;++i) if (b[i]) prim.push_back(i);
    int t;
    fi>>t;
    while (t --)
    {
        fi>>x>>y;
        fo << ans(x,y) << '\n';
    }
    return 0;
}