#include <stdio.h>
#include <stdlib.h>
FILE *fin, *fout;
long long A, B, prod, rasp;
int divi[11];

void pinex(){
  rasp=0;
  int d=2, i, n=0, nr;
  while(d*d<=B){
    i=0;
    while(B%d==0){
      B/=d;
      i++;
    }
    if(i)
      divi[n++]=d;
    d++;
  }
  if(B>1)
    divi[n++]=B;///l-am descompus pe B in factori primi
  for(d=1; d<(1<<n); d++){
    prod=1; nr=0;///explicatiile sunt in word
    for(i=0; i<n; i++)
      if( d&(1<<i) ){
        prod*=divi[i];
        nr++;
      }
    rasp+=(1+(nr%2==0)*(-2))*A/prod;
  }
}

int main(){
  int m;
  fin=fopen("pinex.in", "r");
  fout=fopen("pinex.out", "w");
  fscanf(fin, "%d", &m);
  while(m--){
    fscanf(fin, "%lld %lld", &A, &B);
    pinex();
    fprintf(fout, "%lld\n", A-rasp);
  }
  fclose(fin);
  fclose(fout);
    return 0;
}