#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2")
using namespace std;
const long double eps = 1e-6;
long double inf = 0;
const long long mod = 1e9 + 7;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int count_dels(long long m) {
  int c = 0;
  for (long long i = 1; i * i <= m; ++i) {
    if (m % i != 0) continue;
    ++c;
    if (i != m / i) ++c;
  }
  return c;
}
int main() {
  cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    long long a, m;
    cin >> a >> m;
    long long d = gcd(a, m);
    long long m1 = m / d;
    long long ans = m1;
    for (long long i = 2; i * i <= m1; ++i) {
      if (m1 % i == 0) {
        ans -= ans / i;
        while (m1 % i == 0) m1 /= i;
      }
    }
    if (m1 != 1) ans -= ans / m1;
    cout << ans << "\n";
  }
  return 0;
}
