#include <bits/stdc++.h>
const int N_MAX = 1003;
long long a, m;
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
long long factor[N_MAX];
int cntF;
long long dfs(int x, long long d) {
  if (x > cntF) return std::max(0ll, (m - 1) / d);
  return dfs(x + 1, d) - dfs(x + 1, d * factor[x]);
}
int main() {
  int T;
  for (scanf("%d", &T); T; --T) {
    scanf("%lld%lld", &a, &m);
    long long g = gcd(a, m);
    a /= g, m /= g;
    long long temp = m;
    cntF = 0;
    for (int i = 2; 1ll * i * i <= m; ++i)
      if (temp % i == 0) {
        factor[++cntF] = i;
        while (temp % i == 0) temp /= i;
      }
    if (temp > 1) factor[++cntF] = temp;
    printf("%lld\n", dfs(1, 1));
  }
  return 0;
}
