#include <cstdio>

typedef long long i64;
const int MAXP = 5e5;
const int MAXD = 1e3;
const int MAXC = 1e6;

i64 prim[MAXP + 1], div[MAXD + 1];
bool ciur[MAXC + 1];

int main() {
  int m;
  i64 n, k, a, b, d, p, nr, ans;
  n = 0;
  for (int i = 2; i * i <= MAXC; ++i) {
    if (!ciur[i]) {
      prim[n++] = i;
      for (int j = i * i; j <= MAXC; j += i) {
        ciur[j] = 1;
      }
    }
  }
  FILE *fin = fopen("pinex.in", "r");
  fscanf(fin, "%d", &m);
  FILE *fout = fopen("pinex.out", "w");
  for (; m > 0; --m) {
    fscanf(fin, "%lld%lld", &a, &b);
    d = k = 0;
    while (prim[d] * prim[d] <= b) {
      if (!(b % prim[d])) {
        div[k++] = prim[d];
        while (!(b % prim[d])) {
          b /= prim[d];
        }
      }
      ++d;
    }
    if (b > 1) {
      div[k++] = b;
    }
    ans = 0;               
    for (i64 i = 1; i < (1 << k); ++i) {
      p = 1;
      nr = 0;
      for (i64 j = 0; j <= k; ++j) {
        if (i & (1 << j)) {
          p *= div[j];
          ++nr;
        }
      }
      if (nr & 1) {
        ans += a / p;
      } else {
        ans -= a / p;
      }
    }
    fprintf(fout, "%lld\n", a - ans);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}