#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5;
bool m[N + 2];
vector<long long> primes(1, 2LL);
void sieve() {
  for (int i = 4; i <= N; i += 2) m[i] = 1;
  for (int i = 3; i * i <= N; i += 2)
    if (!m[i])
      for (int j = i * i; j <= N; j += i) m[j] = 1;
  for (int i = 3; i <= N; i += 2)
    if (!m[i]) primes.push_back(i);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15);
  int t;
  cin >> t;
  sieve();
  while (t--) {
    long long a, b;
    cin >> a >> b;
    long long c = 0;
    while (c != 1) {
      c = gcd(a, b);
      a /= c;
      b /= c;
    }
    long long x = b, y = 1;
    for (auto i : primes) {
      if (i > b) break;
      if (b % i == 0) {
        x /= i;
        x *= (i - 1);
        while (b % i == 0) b /= i;
      }
    }
    if (b > 1) {
      x /= b;
      x *= b - 1LL;
    }
    long long res = x / y;
    cout << res << endl;
  }
  return 0;
}
