#include <bits/stdc++.h>
using namespace std;
int const MAX_N = 100000;
vector<long long> prime;
vector<bool> is_prime(MAX_N, true);
void Eratosthenes() {
  is_prime[0] = is_prime[1] = false;
  for (long long i = 2; i * i < MAX_N; ++i)
    if (is_prime[i])
      for (long long j = 2 * i; j < MAX_N; j += i) is_prime[j] = false;
  for (long long i = 0; i < MAX_N; ++i)
    if (is_prime[i]) prime.push_back(i);
}
vector<pair<long long, long long> > prime_factorization(long long a) {
  vector<pair<long long, long long> > prime_factor;
  if (is_prime[0]) Eratosthenes();
  for (long long& i : prime) {
    if (i * i > a) break;
    if (a % i == 0) {
      pair<long long, long long> p = pair<long long, long long>(i, 0);
      while (a % i == 0) {
        a /= i;
        p.second++;
      }
      prime_factor.push_back(p);
    }
  }
  if (a != 1) prime_factor.push_back(pair<long long, long long>(a, 1));
  return prime_factor;
}
void rec(vector<long long>& div, vector<pair<long long, long long> >& fact,
         int i, long long d) {
  if (i == fact.size()) {
    div.push_back(d);
    return;
  }
  for (int j = 0; j <= fact[i].second; ++j) {
    rec(div, fact, i + 1, d);
    d *= fact[i].first;
  }
}
vector<long long> divisor(long long a) {
  vector<long long> div;
  vector<pair<long long, long long> > prime_factor = prime_factorization(a);
  rec(div, prime_factor, 0, 1);
  return div;
}
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int main() {
  int q;
  cin >> q;
  for (int z = 0; z < q; ++z) {
    long long a, m;
    cin >> a >> m;
    m = m / gcd(a, m);
    long long ans = m;
    vector<long long> d = divisor(m);
    sort(d.begin(), d.end());
    map<long long, long long> mp;
    for (long long i : d) {
      if (i == 1) continue;
      if (mp[i] != -1) {
        ans -= m / i * (1 + mp[i]);
        for (long long j : d)
          if (j > i && j % i == 0) mp[j] -= 1 + mp[i];
      }
    }
    cout << ans << "\n";
  }
}
