#include <bits/stdc++.h>

using namespace std;

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

const int NM = 1e6 + 5;

vector<int>primes;
bool c[NM];

void precalc () {
    for (int i = 2; i * i < NM; i++) {
        if (c[i] == 0) {
            for (int j = 2 * i ; j < NM; j += i) {
                c[j] = 1;
            }
        }
    }
    for (int i = 2; i < NM; i++) {
        if (c[i] == 0) {
            primes.push_back(i);
        }
    }
}

int main() {
    precalc();
    int Q; fin >> Q;
    while (Q--) {
        long long a, b;
        fin >> a >> b;
        int d = 0;
        vector<int>fact;
        while (b > 1){
            if (b % primes[d] == 0) {
                fact.push_back(primes[d]);
                while (b % primes[d] == 0) {
                    b /= primes[d];
                }
            }
            ++d;
            if (b > 1 && primes[d] > b / primes[d]) {
                fact.push_back(b);
                break;
            }
        }
        int cnt = (int)fact.size();
        for (int i = 0; i < (1 << cnt); i++) {
            int S = 0, p = 1;
            for (int j = 0; j < cnt; j++) {
                if (i & (1 << j)) {
                    p = 1ll * p * fact[j];
                    ++S;
                }
            }
            if (S % 2 == 1) {
                a = a - a / p;
            }
        }
        fout << a << '\n';
    }
}