#include <stdio.h>

#define MAX_VAL 1000000
#define MAX_P 78500
#define LIMIT 1000
#define Nadejde 20

#define ull long long

ull int A, B, count;
char seen[MAX_VAL + 1];
int size, p[MAX_P];
int N, div[Nadejde];

/** Ciurul lui Eratosthene. **/
void sieve() {
  int i, j, step;

  for (i = 4; i <= MAX_VAL; i += 2) {
    seen[i] = 1;
  }
  for (i = 3; i <= LIMIT; i += 2) {
    if (!seen[i]) {
      p[size++] = i;
      for (step = (i << 1), j = i * i; j <= MAX_VAL; j += step) {
        seen[j] = 1;
      }
    }
  }
  for (; i < MAX_VAL; i += 2) {
    if (!seen[i]) {
      p[size++] = i;
    }
  }
}

/** Obtine divizorii primi ai lui "B". **/
void getDiv() {
  N = count = 0;
  if (B % 2 == 0) {
    div[N++] = 2;
    B /= (-B & B);
  }

  int i;
  for (i = 0; (ull)p[i] * p[i] <= B; i++) {
    if (B % p[i] == 0) {
      div[N++] = p[i];
      do {
        B /= p[i];
      } while (B % p[i] == 0);
    }
  }
  if (B != 1) {
    div[N++] = B;
  }
}

/** Principiul includerii si al excluderii. **/
void bkt(int level, ull int x, int card) {
  if (x > A) {
    return;
  }
  if (level == N) {
    return;
  }
  /* Nu bagam in seama divizorul curent. */
  bkt(level + 1, x, card);

  /* Il bagam in seama. */
  card++;
  x = (ull)x * div[level];

  if (card & 1) {
    count += A / x;
  } else {
    count -= A / x;
  }
  bkt(level + 1, x, card);
}

int main(void) {
  int T;
  FILE *f = fopen("pinex.in", "r");

  sieve();

  /* Citirea datelor si afisarea solutiei. */
  freopen("pinex.out", "w", stdout);
  for (fscanf(f, "%d", &T); T; T--) {
    fscanf(f, "%llu %llu", &A, &B);

    getDiv();
    bkt(0, 1, 0);
    fprintf(stdout, "%llu\n", A - count);
  }
  fclose(f);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}