#include <bits/stdc++.h>
using namespace std;
const int TMAX = 50;
int t;
long long a, m;
long long gcd(long long a, long long b) {
  if (b > a) {
    return gcd(b, a);
  }
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long phi(long long n) {
  long long ans = n, reste = n;
  for (long long d = 2; d * d <= n; d++) {
    if (reste % d == 0) {
      ans *= (d - 1);
      ans /= d;
      while (reste % d == 0) {
        reste /= d;
      }
    }
  }
  if (reste != 1) {
    ans /= reste;
    ans *= (reste - 1);
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> t;
  for (int test = 1; test <= t; test++) {
    cin >> a >> m;
    long long d = gcd(a, m);
    cout << phi(m / d) << '\n';
  }
}
