#include <bits/stdc++.h>
using namespace std;
int T, p[100005];
bool vs[100005];
long long n, m, d, st[100005];
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
void sieve(int n) {
  p[0] = 0;
  vs[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!vs[i]) p[++p[0]] = i;
    for (int j = 1; i * p[j] <= n; ++j) {
      vs[i * p[j]] = 1;
      if (!(i % p[j])) break;
    }
  }
}
void div(long long x) {
  long long t = x;
  st[0] = 0;
  for (int i = 1; i <= p[0] && 1ll * p[i] * p[i] <= x; ++i)
    if (!(t % p[i])) {
      st[++st[0]] = p[i];
      while (!(t % p[i])) t /= p[i];
    }
  if (t > 1) st[++st[0]] = t;
}
long long slv(long long x) {
  long long res = 0, t;
  for (int i = 1, cnt; i < (1 << st[0]); ++i) {
    cnt = 0;
    t = 1;
    for (int j = 1; j <= st[0]; ++j)
      if (i & (1 << j - 1)) ++cnt, t *= st[j];
    if (cnt & 1)
      res += x / t;
    else
      res -= x / t;
  }
  return x - res;
}
int main() {
  sieve(1e5);
  scanf("%d", &T);
  while (T--) {
    scanf("%lld %lld", &n, &m);
    d = gcd(n, m);
    n /= d;
    m /= d;
    div(m);
    printf("%lld\n", slv(n + m - 1) - slv(n - 1));
  }
  return 0;
}
