#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 5;
typedef long long i64;

i64 gcd(i64 a, i64 b) {
    for (i64 t; b; t = a, a = b, b = t % a);
    return a;
}

char is_prime[MAX_N];
int pn, prime[MAX_N / 10];

int main() {
    vector<i64> vm;
    i64 T, a, m, M = 0;
    for (scanf("%lld", &T); T --; ) {
        i64 a, m;
        scanf("%lld%lld", &a, &m);
        m /= gcd(a, m);
        vm.push_back(m);
        M = max(M, m);
    }
    M = sqrt(M);
    for (int i = 2; i <= M; i ++) {
        is_prime[i] = 1;
    }
    for (int i = 2; i <= M; i ++) {
        if (is_prime[i]) {
            prime[++ pn] = i;
        }
        for (int j = 1; j <= pn && i * prime[j] <= M; j ++) {
            is_prime[i * prime[j]] = 0;
        }
    }
    for (i64 m: vm) {
        i64 t = m;
        for (int j = 1; j <= pn; j ++) {
            int p = prime[j];
            if (m % p == 0) {
                t = t / p * (p - 1);
                do {
                    m /= p;
                } while (m % p == 0);
            }
        }
        if (m > 1) {
            t = t / m * (m - 1);
        }
        printf("%lld\n", t);
    }
    return 0;
}