#include <bits/stdc++.h>
using namespace std;
long long a, m, times;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  if (b > a) return gcd(b, a);
  return gcd(b, a % b);
}
vector<long long> primes;
bool not_prime[100010];
int main() {
  primes.push_back(2);
  for (long long i = 3; i <= 100000; i += 2) {
    if (!not_prime[i]) primes.push_back(i);
    for (long long j = i * i; j <= 100000; j += 2 * i) not_prime[j] = true;
  }
  cin >> times;
  while (times--) {
    cin >> a >> m;
    long long g = gcd(a, m);
    m /= g;
    long long ans = m;
    for (long long p = 0; p < primes.size(); p++) {
      if (m % primes[p] == 0) ans = (ans / primes[p]) * (primes[p] - 1);
      while (m % primes[p] == 0) m /= primes[p];
    }
    if (m != 1) ans = (ans / m) * (m - 1);
    cout << ans << "\n";
  }
}
