#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

typedef long long ll;
const int NMAX = 16;
const int LMAX = (1 << 16);
const int HMAX = 1000505;
int tests, nbits[LMAX], P[HMAX], r, bit[LMAX];
ll maskDiv[LMAX], a, b;
bitset<HMAX> notPrime;

void prepare() {
  for (int i = 2; i * i < HMAX; i++)
    if (!notPrime[i]) {
      for (int j = i * i; j < HMAX; j += i)
        notPrime[j] = 1;
    }

  for (int i = 2; i < HMAX; i++)
    if (!notPrime[i]) {
      P[++r] = i;
    }

  for (int i = 1; i <= NMAX; i++) {
    bit[1 << (i - 1)] = i;
  }
}

vector<ll> decompose(ll no) {
  vector<ll> sol;
  for (int i = 1; 1LL * P[i] * P[i] <= no; i++)
    if (no % P[i] == 0) {
      sol.push_back(P[i]);
      while (no % P[i] == 0) {
        no /= P[i];
      }
    }
  if (no != 1) {
    sol.push_back(no);
  }

  return sol;
}

int lsb(int x) {
  return x & -x;
}

inline ll f(ll a, ll b) {
  return a / b;
}

ll pinex(ll no, vector<ll>& divs) {
  int N = divs.size();
  maskDiv[0] = 1;
  ll res = 0;
  for (int mask = 1; mask < (1 << N); mask++) {
    nbits[mask] = nbits[mask >> 1] + (mask & 1);
    maskDiv[mask] = maskDiv[mask - lsb(mask)] * divs[bit[lsb(mask)] - 1];
    res += f(no, maskDiv[mask]) * ((nbits[mask] & 1) ? 1 : -1);
  }

  return res;
}

void solve() {
  scanf("%d", &tests);
  while (tests--) {
    scanf("%lld%lld", &a, &b);

    vector<ll> divs = decompose(b);
    printf("%lld\n", a - pinex(a, divs));
  }
}

int main() {
  freopen("pinex.in", "r", stdin);
  freopen("pinex.out", "w", stdout);

  prepare();
  solve();
  return 0;
}