#include <cstdio>
#include <cmath>

long long div[30];

bool ciur[10000005];
int prime[10000005];

void Ciur() {
  ciur[1] = ciur[0] = 1;
  for (int i = 4; i <= 10000000; i += 2) {
    ciur[i] = 2;
  }
  for (int i = 3; i * i <= 10000000; i += 2) {
    if (!ciur[i]) {
      for (int j = i * i; j <= 10000000; j += 2 * i) {
        ciur[j] = true;
      }
    }
  }
  int k;
  k = 1;
  prime[k] = 2;
  for (int i = 3; i <= 10000000; i += 2) {
    if (!ciur[i]) {
      prime[++k] = i;
    }
  }
}

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

  long long M, A, B;
  scanf("%lld", &M);
  Ciur();
  for (int i = 1; i <= M; i++) {
    scanf("%lld %lld", &A, &B);
    long long k, d, x;
    k = 0;
    x = 1;
    d = prime[x];
    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;
      }
      d = prime[++x];
    }
    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;
}