#include <bits/stdc++.h>
using namespace std;
class Quick_Input_Output {
 private:
  static const long long S = 1 << 21;
  char Rd[S], *A, *B;

 public:
  inline long long read() {
    long long res = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
      if (ch == '-') f = -1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * f;
  }
  inline void write(long long x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10)
      putchar(x + '0');
    else
      write(x / 10), putchar(x % 10 + '0');
  }
} I;
long long T, a, m;
inline long long get(long long x) {
  long long res = x;
  for (long long i = 2; i <= sqrt(x); i++) {
    if (x % i == 0) {
      res /= i;
      res *= (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x != 1) res /= x, res *= x - 1;
  return res;
}
inline long long gcd(long long a, long long b) {
  return b == 0 ? a : gcd(b, a % b);
}
signed main() {
  T = I.read();
  while (T--) {
    a = I.read();
    m = I.read();
    I.write(get(m / gcd(a, m)));
    putchar('\n');
  }
}
