#include <cstdio>
#include <cmath>

long long div[30];

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

  long long M, A, B;
  scanf("%lld", &M);
  for (int i = 1; i <= M; i++) {
    scanf("%lld %lld", &A, &B);
    long long k, d;
    k = 0;
    d = 2;
    while (B > 1) {
      if (B % d == 0) {
        div[++k] = d;
        while (B % d == 0) {
          B /= d;
        }
      }
      if (d > sqrt(B) && B > 1) {
        div[++k] = B;
        B = 1;
      }
      if (d == 2) {
        d++;
      } else {
        d += 2;
      }
    }
    long long ans = A;
    for (int i = 1; i < (1 << k); i++) {
      long long nr = 0, p = 1;
      for (int j = 0; j < k; j++) {
        if ( (1 << j) & i) {
          p = 1LL * p * div[j + 1];
          nr++;
        }
      }
      if (nr % 2) {
        nr = -1;
      }
      else {
        nr = 1;
      }
      ans = ans + 1LL * nr * A / p;
    }
    printf ("%lld\n", ans);
  }
  return 0;
}