#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 9973;
const double eps = 1e-8;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
int max(int x, int y) {
  if (x > y) return x;
  return y;
}
long long powmod(long long a, long long b) {
  unsigned long long ans = 1, pow = a % mod;
  while (b) {
    if (b & 1) ans = (ans * pow) % mod;
    pow = (pow * pow) % mod;
    b >>= 1;
  }
  return ans % mod;
}
int T;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> T;
  while (T--) {
    long long a, b;
    cin >> a >> b;
    long long cnt = gcd(a, b);
    b /= cnt;
    long long ans = b;
    for (long long i = 2; i * i <= b; i++) {
      if (b % i == 0) {
        ans -= ans / i;
        while (b % i == 0) {
          b /= i;
        }
      }
    }
    if (b > 1) {
      ans -= ans / b;
    }
    cout << ans << '\n';
  }
  return 0;
}
