#include<bits/stdc++.h>
using namespace std;
#define int long long


int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a;
}
int phi(int x) {
    int res = x;
    int a = x;
    for (int i = 2;i * i <= x;i++) {
        if (a % i == 0) {
            res = res / i * (i - 1);
        }
        while (a % i == 0)
            a = a / i;
    }
    if (a > 1) {
        res = res / a * (a - 1);
    }
    return res;
}
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int a, m;
        cin>>a>>m;
        int k = gcd(a, m);
        int x = phi(m / k);
        cout << x << endl;
    }
    return 0;
}