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

using namespace std;

const int nmax = 1e6 + 2;
bool not_prime[nmax], f[nmax];
vector<int> p, dv;
int lim, n, ans;

void calc (int pos, int st, int len, int val, int x) {
    if (val > lim)
        return;
    if (pos == len + 1) {
        ans += x * (lim / val);
        return;
    }
    for (int i = st; i < dv.size(); i++)
        if (!f[i]) {
            f[i] = true;
            calc(pos + 1, i + 1, len, val * dv[i], x);
            f[i] = false;
        }
}

void solve () {
    ans = 0;
    dv.clear();
    cin >> lim >> n;
    int cop = n;
    for (auto d : p) {
        if (d > n)
            break;
        if (n % d == 0) {
            dv.push_back(d);
            while (n % d == 0)
                n /= d;
        }
    }
    if (n != 1)
        dv.push_back(n);
    int x = 1;
    for (int len = 1; len <= dv.size(); len++) {
        for (int i = 0; i < dv.size(); i++)
            f[i] = false;
        calc(1, 0, len, 1, x);
        x *= -1;
    }
    cout << lim - ans << '\n';
}

signed main () {
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    not_prime[1] = true;
    for (int i = 2; i < nmax; i++)
        if (!not_prime[i]) {
            p.push_back(i);
            for (int j = i * i; j < nmax; j += i)
                not_prime[j] = true;
        }
    int T; cin >> T;
    while (T--)
        solve();
}