#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline vector<T> readvector(size_t size) {
  vector<T> res(size);
  for (size_t i = 0; i < size; ++i) {
    cin >> res[i];
  }
  return res;
}
template <typename T>
inline void printvector(vector<T> &arr, string sep = " ", string ends = "\n") {
  for (size_t i = 0; i < arr.size(); ++i) {
  }
}
inline long long binPow(long long first, long long deg, long long mod) {
  long long ans = 1;
  for (long long i = sizeof(first) * CHAR_BIT - 1; i >= 0; i--) {
    ans *= ans;
    ans %= mod;
    if ((((deg) >> (i)) & 1)) ans *= first;
    ans %= mod;
  }
  return ans;
}
const long long MAXN = 2e5 + 10;
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  if (n > 1) result -= result / n;
  return result;
}
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long a, m;
    cin >> a >> m;
    long long d = gcd(a, m);
    long long first = phi(m / d);
    cout << first << endl;
  }
  return 0;
}
