#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MAXN = 5 + 1000000;
vector<ll> primes;
bitset<MAXN> isp;
void sieve() {
  isp.set();
  for (ll i = 2; i < MAXN; i++) {
    if (isp[i]) {
      for (ll j = i * i; j < MAXN; j += i) {
        isp[j] = false;
      }
      primes.push_back(i);
    }
  }
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
set<ll> factor(ll x) {
  set<ll> res;
  for (int i = 0; i < (int)primes.size() && primes[i] * primes[i] <= x; ++i) {
    int c = 0;
    while ((x % primes[i]) == 0) {
      c++;
      x /= primes[i];
    }
    if (c) {
      res.insert(primes[i]);
    }
  }
  if (x != 1) res.insert(x);
  return res;
}
ll solve(int idx, ll res, int p, const vector<ll>& v, ll ans) {
  if (idx == (int)v.size()) {
    ll r = ans / res;
    if (p & 1) return r;
    return -r;
  } else {
    return solve(1 + idx, res * v[idx], p ^ 1, v, ans) +
           solve(1 + idx, res, p, v, ans);
  }
}
ll count(ll lim, ll m, ll g) {
  if (lim < 1) return 0LL;
  ll ans = lim / g;
  set<ll> f = factor(m / g);
  vector<ll> wtf(f.begin(), f.end());
  return solve(0, 1, 0, wtf, ans);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  sieve();
  int tc;
  cin >> tc;
  while (tc--) {
    ll a, m;
    cin >> a >> m;
    ll g = gcd(a, m);
    cout << -(count(a + m - 1, m, g) - count(a - 1, m, g)) << '\n';
  }
  return 0;
}
