#include <iostream>

using namespace std;

int divs[13], nrbits1[(1 << 13)];
long long cmmmc[(1 << 13)];

int desc(long long val) {
  int ndiv, exp, p;

  p = 2;
  ndiv = 0;
  while (val > 1 && p * p <= val) {
    exp = 0;
    while (val % p == 0) {
      val /= p;
      exp++;
    }

    if (exp > 0)
      divs[ndiv++] = p;

    p++;
  }

  if (val > 1)
    divs[ndiv++] = val;
  return ndiv;
}

int lcm(int a, int b) {
  int r, ca, cb;

  ca = a; cb = b;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }

  return (ca * cb) / a;
}

long long solve(long long a, long long b) {
  int ndiv, j, i, mask;
  long long sol;

  ndiv = desc(b);

  cmmmc[0] = 1;
  nrbits1[0] = sol = 0;
  for (i = 1; i < (1 << ndiv); i++) {
    j = 0;
    while (j < ndiv && !(i & (1 << j)))
      j++;

    mask = (i ^ (1 << j));
    cmmmc[i] = lcm(cmmmc[mask], divs[j]);
    nrbits1[i] = nrbits1[mask] + 1;

    if (nrbits1[i] % 2 == 1)
      sol += (a / cmmmc[i]);
    else
      sol -= (a / cmmmc[i]);
  }

  return sol;
}

signed main() {
  FILE *fin, *fout;
  int n;
  long long a, b;

  fin = fopen("pinex.in", "r");
  fscanf(fin, "%d", &n);

  fout = fopen("pinex.out", "w");
  while (n--) {
    fscanf(fin, "%lld%lld", &a, &b);
    fprintf(fout, "%lld\n", a - solve(a, b));
  }

  fclose( fin );
  fclose ( fout );
  return 0;
}