#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e6;
long long int gcd(long long int a, long long int b) {
  if (a > b) swap(a, b);
  if (a == 0) return b;
  return gcd(b % a, a);
}
void eulerTotient(long long int m) {
  vector<long long int> fact;
  long long int ans = m;
  for (long long int i = 2; i <= sqrt(m); ++i) {
    if (m % i == 0) {
      fact.push_back(i);
      while (m % i == 0) m /= i;
    }
  }
  if (m > 1) fact.push_back(m);
  for (long long int i = 0; i < fact.size(); ++i) {
    ans = ans - (ans / fact[i]);
  }
  cout << ans << endl;
}
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  while (t-- > 0) {
    long long int a, m;
    cin >> a >> m;
    long long int p = gcd(a, m);
    m /= p;
    eulerTotient(m);
  }
}
