#include <stdio.h>
#define MAXCIUR 1000000
#define MAXPRIME 78498
#define MAXDIV 12
char npr[MAXCIUR + 1];
int prime[MAXPRIME], primb[MAXDIV];

void ciur(int n){
  int i, j, dr = 0;
  for(i = 2; i * i <= n; i++){
    if(!npr[i]){
      prime[dr] = i;
      dr++;
      for(j = i * i; j <= n; j += i){
        npr[j] = 1;
      }
    }
  }
  for( ; i <= n; i++ ){
    if(!npr[i]){
      prime[dr] = i;
      dr++;
    }
  }
}

long long diviz(long long a, long long b){
  int i, dr = 0;
  for(i = 0; prime[i] * prime[i] <= b && i < MAXPRIME; i++){
    if(b % prime[i] == 0){
      primb[dr] = prime[i];
      dr++;
    }
    while(b % prime[i] == 0){
      b /= prime[i];
    }
  }
  if(b > 1){
    primb[dr] = b;
    dr++;
  }
  int ci, p, minus;
  long long rez = 0, nr;
  for(i = 1; i < (1 << dr); i++){
    p = 0;
    nr = 1;
    minus = -1;
    for(ci = i; ci > 0; ci >>= 1){
      if(ci & 1){
        nr *= primb[p];
        minus = -minus;
      }
      p++;
    }
    rez += minus * (a / nr);
  }
  return rez;
}

int main(){
  FILE *in = fopen("pinex.in", "r");
  FILE *out = fopen("pinex.out", "w");
  ciur(MAXCIUR);
  int n, i;
  long long a, b;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%lld%lld", &a, &b);
    fprintf(out, "%lld\n", a - diviz(a, b));
  }
  fclose(in);
  fclose(out);
  return 0;
}