#include <bits/stdc++.h>
using namespace std;
long long int gcd(long long int a, long long int b) {
  if (b < a) {
    long long int tmp = b;
    b = a;
    a = b;
  }
  while (b != 0) {
    long long int tmp = b;
    b = a % b;
    a = tmp;
  }
  return a;
}
int main() {
  int tests;
  cin >> tests;
  for (int t = 0; t < tests; ++t) {
    long long int a, m;
    cin >> a >> m;
    m = m / gcd(a, m);
    long long int m2 = m, m3 = m;
    for (long long int i = 2LL; i * i <= m && i <= m2; i += 2LL) {
      if (m2 % i == 0) {
        m3 /= i;
        m3 *= i - 1LL;
        while (m2 % i == 0LL) {
          m2 /= i;
        }
      }
      if (i == 2LL) --i;
    }
    if (m3 == m) {
      cout << m - 1LL << endl;
    } else if (m2 > 1) {
      cout << (m3 / m2) * (m2 - 1LL) << endl;
    } else {
      cout << m3 << endl;
    }
  }
  return 0;
}
