#include <bits/stdc++.h>
using namespace std;
vector<long long> v1, v2;
long long N, M, K, Q, T;
vector<long long> vl;
vector<vector<long long> > vadj;
long long GCD(long long a, long long b) {
  if (a == 0) return b;
  if (b == 0) return a;
  return GCD(b % a, a);
}
map<long long, bool> mp;
long long ans2 = 0;
long long multinf;
long long multsup;
void menn(long long index, long long num, long long mult) {
  if (index == vl.size()) {
    long long pachecar = 1;
    long long check = 0;
    for (int i = 0; i < vl.size(); i++) {
      if (num % 2 == 1) {
        pachecar *= vl[i];
        check++;
      }
      num /= 2;
    }
    if (pachecar != 1) {
      long long cuantos = (multinf - 1) / pachecar - multsup / pachecar;
      if (check % 2 == 1)
        ans2 += cuantos;
      else
        ans2 -= cuantos;
    }
    return;
  }
  menn(index + 1, num, mult * 2);
  menn(index + 1, num + mult, mult * 2);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> T;
  for (long long k = 0; k < T; k++) {
    mp.clear();
    vl.clear();
    long long a, b;
    ans2 = 0;
    cin >> a >> b;
    long long gcd = GCD(a, b);
    long long inf = a;
    long long sup = a + b - 1;
    multinf = a / gcd;
    if (multinf * gcd < a) multinf++;
    multsup = sup / gcd;
    b /= gcd;
    for (long long i = 2; i * i <= b; i++) {
      if (b % i == 0) {
        if (mp[i] == false) vl.push_back(i);
        mp[i] = true;
        b /= i;
        i = 1;
      }
    }
    if (mp[b] == false) vl.push_back(b);
    menn(0, 0, 1);
    long long cuan = multsup - multinf + 1;
    cuan += ans2;
    cout << cuan << endl;
  }
}
