#include <stdio.h>
#include <math.h>

#define ll long long

ll M, A, B, fact[30];

void solve() {
  ll t = 0, d = 2;
  while (B > 1) {
    if (B % d == 0) {
      fact[++t] = d;
      while (B % d == 0)
        B /= d;
    }
    if (d > sqrt(B) && B > 1) {
      fact[++t] = B;
      B = 1;
    }
    if (d == 2)
      d++;
    else
      d += 2;
  }
  ll sol = A;
  for (int i = 1; i < (1 << t); i++) {
    ll nr = 0, prod = 1;
    for (int j = 0; j < t; j++)
      if ((1 << j) & i) {
        prod = 1LL * prod * fact[j + 1];
        nr++;
      }
    if (nr % 2)
      nr = -1;
    else
      nr = 1;
    sol = sol + 1LL * nr * A / prod;
  }
  printf("%lld\n", sol);
}

int main() {
  freopen("pinex.in", "r", stdin);
  freopen("pinex.out", "w", stdout);
  scanf("%lld", &M);
  for (int i = 1; i <= M; i++) {
    scanf("%lld %lld", &A, &B);
    solve();
  }
  return 0;
}