#include <bits/stdc++.h>
using namespace std;
using int32 = int_fast32_t;
using int64 = int_fast64_t;
const int32 INF = 1e9;
const int32 MOD = 1e9 + 7;
const int64 LLINF = 1e18;
int64 gcd(int64 a, int64 b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
map<int64, int64> factorization(int64 n) {
  map<int64, int64> res;
  for (int64 p = 2; p * p <= n; p++) {
    while (n % p == 0) {
      res[p]++;
      n /= p;
    }
  }
  if (n != 1) res[n]++;
  return res;
}
int64 mypow(int64 n, int64 r) {
  if (r == 0) return 1;
  if (r % 2 == 0) {
    int64 x = mypow(n, r / 2);
    return x * x;
  } else {
    return mypow(n, r - 1) * n;
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 t;
  cin >> t;
  while (t--) {
    int64 a, m;
    cin >> a >> m;
    int64 g = gcd(a, m);
    map<int64, int64> faca, facm;
    faca = factorization(a);
    facm = factorization(m);
    vector<int64> diff;
    for (auto p : facm) {
      int64 n, r;
      tie(n, r) = p;
      if (r > faca[n]) diff.push_back(n);
    }
    int64 l = (a + g - 1) / g;
    int64 r = (a + m + g - 1) / g;
    int64 ans = r - l;
    int64 n = diff.size();
    for (int s = 1; s < (1 << n); ++s) {
      int64 lcm = 1;
      for (int64 i = 0; i < (n); ++i) {
        if ((s >> i) & 1) {
          lcm *= diff[i];
        }
      }
      int64 cnt = bitset<32>(s).count();
      if (cnt % 2 == 1) {
        ans -= (r - 1) / lcm - (l - 1) / lcm;
      } else {
        ans += (r - 1) / lcm - (l - 1) / lcm;
      }
    }
    cout << (ans) << "\n";
  }
  return 0;
}
