#include <fstream>
#include <cmath>

#define ll long long

using namespace std;

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

ll M, A, B, fact[30];

void solve() {
    ll t = 0, d = 2;
    ll b = B; // Copiem B pentru a nu-l altera

    while (b > 1) {
        if (b % d == 0) {
            fact[++t] = d;
            while (b % d == 0)
                b /= d;
        }

        if (d > sqrt(b) && b > 1) {
            fact[++t] = b;
            b = 1;
        }

        if (d == 2) d++;
        else d += 2;
    }

    ll sol = A;
    for (int i = 1; i < (1 << t); i++) {
        ll nr = 0, prod = 1;
        for (int j = 0; j < t; j++) {
            if ((1 << j) & i) {
                prod *= fact[j + 1];
                nr++;
            }
        }

        if (nr % 2) nr = -1;
        else nr = 1;

        sol += nr * (A / prod);
    }

    cout << sol << "\n";
}

int main() {

    cin >> M;
    for (int i = 1; i <= M; i++) {
        cin >> A >> B;
        solve();
    }

    return 0;
}