#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 9;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int pmax = 1e6;
bitset<pmax + 5> sieve;
vector<int> primes;

void precomputing() {
    sieve.set();
    for (int i = 2; i <= pmax; ++i) {
        if (sieve[i]) {
            primes.push_back(i);
            for (ll j = 1ll * i * i; j <= pmax; j += i) {
                sieve[j] = 0;
            }
        }
    }
}

void testcase() {
    long long a, b;
    fin >> a >> b;
    vector<int> factors;
    for (auto& p : primes) {
        if (b / p / p < 1) {
            break;
        }
        if (b % p == 0) {
            factors.push_back(p);
            while (b % p == 0) {
                b /= p;
            }
        }
    }
    if (b > 1) {
        factors.push_back(b);
    }
    int lg = factors.size();
    ll cnt = 0;
    for (int mask = 0; mask < (1 << lg); ++mask) {
        ll divisor = 1;
        for (int i = 0; i < mask; ++i) {
            if ((mask >> i) & 1) {
                divisor *= -factors[i];
            }
        }
        cnt += a / divisor;
    }
    fout << cnt << nl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    precomputing();
    int tc;
    fin >> tc;
    for (int t = 1; t <= tc; ++t) {
#ifdef LOCAL
        cerr << "=== Subtask " << t << " ===" << nl;
#endif
        testcase();
#ifdef LOCAL
        cerr << nl;
#endif
    }
}