#include <bits/stdc++.h>
using namespace std;
long long calc_gcd(long long a, long long b) {
  while (true)
    if (a)
      b %= a, swap(a, b);
    else
      return b;
}
void foo() {
  long long A, M;
  cin >> A >> M;
  long long gcd = calc_gcd(A, M);
  A /= gcd;
  M /= gcd;
  set<long long> yakusuu;
  long long tmp = M;
  while (tmp % 2 == 0) {
    yakusuu.insert(2);
    tmp /= 2;
  }
  for (long long i = 3; i * i <= M; i += 2) {
    while (tmp % i == 0) {
      yakusuu.insert(i);
      tmp /= i;
    }
  }
  if (tmp > 1) {
    yakusuu.insert(tmp);
    tmp = 1;
  }
  vector<long long> yakusuu_vec;
  for (auto it : yakusuu) yakusuu_vec.push_back(it);
  long long limit = 1;
  limit <<= yakusuu_vec.size();
  long long foo = 0;
  long long bar = 0;
  for (long long i = 0; i < limit; i++) {
    long long tmp = 1;
    long long count = 0;
    for (long long k = 0; k < (yakusuu_vec.size()); k++) {
      if (((i >> k) & 1) == 1) {
        tmp *= yakusuu_vec[k];
        count++;
      }
    }
    if (count % 2) {
      foo -= (A + M - 1) / tmp;
      bar -= (A - 1) / tmp;
    } else {
      foo += (A + M - 1) / tmp;
      bar += (A - 1) / tmp;
    }
  }
  cout << (foo - bar) << endl;
}
void solve() {
  long long T;
  cin >> T;
  for (long long t = 0; t < (T); t++) foo();
}
int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  cout << fixed;
  solve();
  return 0;
}
