#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int MAX = 1e6;

bool ciur[MAX + 5];
vector <int> prime;
int factori[30];

void precalculare() {
    ciur[0] = ciur[1] = 1;

    for (int i = 2; i <= MAX; i++) {
        if (!ciur[i]) {
            prime.push_back(i);

            for (int j = 2 * i; j < MAX; j += i) {
                ciur[j] = 1;
            }
        }
    }
}

void solve() {
    long long a, b;
    fin >> a >> b;

    int f = 0;
    for (int i = 0; i < prime.size(); i++) {
        if (1LL * prime[i] * prime[i] > b) break;

        if (b % prime[i] == 0) {
            factori[++f] = prime[i];

            while (b % prime[i] == 0) {
                b /= prime[i];
            }
        }
    }

    if (b > 1) factori[++f] = b;

    long long ans = a;
    for (int mask = 1; mask < (1 << f); mask++) {
        long long nr_biti = 0, p = 1;

        for (int i = 0; i < f; i++) {
            if (mask & (1 << i)) {
                nr_biti++;
                p *= 1LL * factori[i + 1];
            }
        }

        long long ok = (nr_biti % 2 == 1) ? -1 : 1;

        ans += 1LL * ok * (a / p);
    }

    fout << ans << '\n';
}

int main()
{
    precalculare();

    int m;
    fin >> m;

    while (m--) {
        solve();
    }
    return 0;
}