#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream in ("pinex.in");
ofstream out ("pinex.out");

const int VMAX = 1e6 + 100;
bitset<VMAX + 5>v;
vector<int>p;

void solve ()
{
    int n, m;
    in >> n >> m;
    int d=0;
    vector<int>divs;
    while (p[d] * p[d] <= m)
    {
        if (m % p[d] == 0)
        {
            divs.push_back(p[d]);
            m /= p[d];
            while (m % p[d] == 0)
                m /= p[d];
        }
        d++;
    }
    if (m > 1)
        divs.push_back(m);
    int sz = (int)divs.size();
    int ans = 0;
    for (int i=0; i<(1<<sz); i++)
    {
        int nr = 1;
        for (int j=0; j<sz; j++)
        {
            if (i & (1 << j))
                nr *= divs[j];
        }
        if (__builtin_popcount(i) % 2 == 0)
            ans += (n / nr);
        else
            ans -= (n / nr);
    }
    out << ans << '\n';
}

signed main()
{
    for (int i=3; i*i<VMAX; i+=2)
    {
        if (!v[i])
        {
            for (int j=i*i; j<VMAX; j+=i+i)
                v[j] = 1;
        }
    }

    p.push_back(2);
    for (int i=3; i<VMAX; i+=2)
    {
        if (!v[i])
            p.push_back(i);
    }

    int q;
    in >> q;
    while (q--)
        solve();

    return 0;
}