#include <bits/stdc++.h>

#define int long long

using namespace std;

int tc, A, B;
vector<int> prime;

vector<int> sieve(int _n) {
    vector<int> _ans;
    bool _isPrime[_n + 10];
    memset(_isPrime, false, sizeof(_isPrime));
    _isPrime[1] = true;
    for (int i = 2; i <= _n; i++)
        if (!_isPrime[i]) {
            _ans.push_back(i);
            for (int j = i * i; j <= _n; j += i)
                _isPrime[j] = true;
        }
    return _ans;
}

void solve() {
    cin >> A >> B;
    vector<int> p;
    for (auto f: prime)
        if (B % f == 0) p.push_back(f);

    int mx = (1 << p.size()) - 1, cnt = 0;
    for (int mask = 1; mask <= mx; mask++) {
        int semn = 1;
        if (__builtin_popcount(mask) % 2 == 0) semn = -1;
        int prod = 1;
        for (int bit = 0; bit < p.size(); bit++)
            if ((1 << bit) & mask) prod *= p[bit];
        cnt += (A / prod) * semn;
    }
    cout << A - cnt << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    prime = sieve((int) 1e6);

    cin >> tc;
    while (tc--) {
        solve();
    }
}