#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
ll a, m;
void init() {}
void input() { cin >> a >> m; }
ll gcd(ll a, ll b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
void solve() {
  vector<ll> prime;
  ll g = gcd(a, m);
  a /= g;
  m /= g;
  ll n = m;
  ll d = 2;
  while (d * d <= n) {
    if (n % d == 0) {
      prime.push_back(d);
    }
    while (n % d == 0) {
      n /= d;
    }
    d++;
  }
  if (n > 1) {
    prime.push_back(n);
  }
  ll ans = 0;
  ll len = int(prime.size());
  for (ll mask = 0; mask < (1 << len); mask++) {
    ll inst = mask;
    ll div = 1;
    for (int i = 0; i < len; i++) {
      if (inst % 2) {
        div *= -prime[i];
      }
      inst /= 2;
    }
    ans += (m + a - 1) / div - (a - 1) / div;
  }
  cout << ans << endl;
}
void output() {}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int number_of_testcases = 1;
  cin >> number_of_testcases;
  while (number_of_testcases--) {
    init();
    input();
    solve();
    output();
  }
  return 0;
}
