#include <bits/stdc++.h>
using namespace std;
long long inline read() {
  long long num = 0, neg = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num * neg;
}
const long long maxn = 200010;
long long T;
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
long long vis[maxn], p[maxn], len;
void Get() {
  for (long long i = 2; i <= 100000; i++) {
    if (vis[i]) continue;
    p[++len] = i;
    for (long long j = 2; i * j <= 100000; j++) vis[i * j] = 1;
  }
}
long long Getphi(long long x) {
  long long ans = x;
  for (long long i = 1; i <= len; i++)
    if (x % p[i] == 0) {
      ans = ans / p[i] * (p[i] - 1);
      while (x % p[i] == 0) x /= p[i];
    }
  if (x != 1) ans = ans / x * (x - 1);
  return ans;
}
signed main() {
  T = read();
  Get();
  while (T--) {
    long long a = read(), m = read();
    long long d = gcd(a, m);
    cout << Getphi(m / gcd(a, m)) << endl;
  }
  return 0;
}
