#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 1000000;

bool sieve[MAXN + 5];
vector<int> primes;

void precompute() {
    for (int i = 2; i <= MAXN; i++) {
        if (!sieve[i]) {
            primes.push_back(i);
            for (int j = i + i; j <= MAXN; j += i) {
                sieve[j] = true;
            }
        }
    }
}

void solve() {
    long long a, b;
    in >> a >> b;
    vector<int> factors;
    for (int i = 0; primes[i] * primes[i] <= b; i++) {
        if (b % primes[i] == 0) {
            factors.push_back(primes[i]);
            while (b % primes[i] == 0) {
                b /= primes[i];
            }
        }
    }
    if (b > 1) {
        factors.push_back(b);
    }
    long long ans = a;
    for (int mask = 1; mask < (1 << factors.size()); mask++) {
        long long bits = 0, p = 1;
        for (int bit = 0; (1 << bit) <= mask; bit++) {
            if ((1 << bit) & mask) {
                p = 1LL * p * factors[bit];
                bits++;
            }
        }
        ans = ans + 1LL * (bits % 2 ? -1 : 1) * a / p;
    }
    out << ans << '\n';
}

int main() {

    int q;
    in >> q;

    precompute();

    while (q--) {
        solve();
    }

    return 0;
}