#include <cstdio>

const int MAX_X = 1000000;
const int MAX_PRIME = 80000;
bool ciur[MAX_X];
long long prime[MAX_PRIME];
long long desc[20];

long long pinex(long long a, long long b) {
  int d, pr, bits;
  long long prod, rez;
  d = 0;
  pr = 0;
  while(prime[d] * prime[d] <= b) {
    if(b % prime[d] == 0) {
      desc[pr] = prime[d];
      while(b % prime[d] == 0)
        b = b / prime[d];
      ++pr;
    }
    ++d;
  }
  if(b > 1) {
    desc[pr] = b;
    ++pr;
  }

  rez = 0LL;
  for(int i = 0; i < (1 << pr); ++i) {
    prod = 1LL;
    bits = 0;
    for(int j = 0; j < pr; ++j)
      if(1 << j & i) {
        ++bits;
        prod = prod * desc[j];
      }
    if(bits % 2 == 0)
      rez = rez + a / prod;
    else
      rez = rez - a / prod;
  }
  return rez;
}

int main() {
  int n, top;
  long long a, b;

  for(int d = 2; d * d <= MAX_X; ++d)
    if(!ciur[d])
      for(int i = d * d; i <= MAX_X; i = i + d)
        ciur[i] = true;

  top = 0;
  for(int d = 2; d <= MAX_X; ++d)
    if(!ciur[d]) {
      prime[top] = d;
      top++;
    }
  FILE *fin = fopen("pinex.in", "r");
  FILE *fout = fopen("pinex.out", "w");
  fscanf(fin, "%d", &n);
  for(int i = 0; i < n; ++i) {
    fscanf(fin, "%lld%lld", &a, &b);
    fprintf(fout, "%lld\n", pinex(a, b));
  }
  fclose(fin);
  fclose(fout);
  return 0;
}