#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    long long a, m;
    cin >> a >> m;
    long long g = gcd(a, m);
    long long temp_m = m / g;
    vector<long long> primes;
    for (long long i = 2; i * i <= temp_m; i++) {
      if (temp_m % i == 0) {
        primes.push_back(i);
      }
      while (temp_m % i == 0) {
        temp_m /= i;
      }
    }
    if (temp_m > 1) {
      primes.push_back(temp_m);
    }
    int n = primes.size();
    long long start = a - 1;
    long long end = a + m - 1;
    long long solution = end / g - start / g;
    for (int i = 1; i < (1 << n); i++) {
      bitset<10> bit_set(i);
      long long num = g;
      int parity = 0;
      for (int j = 0; j < n; j++) {
        if (bit_set[j] == 1) {
          num *= primes[j];
          parity++;
        }
      }
      long long ans = end / num - start / num;
      if (parity % 2 == 0) {
        solution += ans;
      } else {
        solution -= ans;
      }
    }
    cout << solution << "\n";
  }
  return 0;
}
