#include <stdio.h>

char npr[1000000 + 1];
int prima[78498], primb[12];
 
void ciur(int n){
  int dr=0,i;
  for(i=2;i*i<=n;i++)
  {
    if(npr[i]!=1)
    {
      prima[dr]=i;
      dr++;
      for(int j=i*i;j<=n;j+=i)  npr[j]=1;
    }
  }
  for( ;i<=n;i++)
  {
    if(npr[i]!=1)
    {
      prima[dr]=i;
      dr++;
    }
  }
}
 
long long diviz(long long a, long long b){
  int i, dr = 0;
  for(i=0;1LL*prima[i]*prima[i]<=b && i<78498;i++)
  {
    if(b%prima[i]==0)
    {
      primb[dr]=prima[i];
      dr++;
    }
    while(b % prima[i] == 0){
      b /= prima[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*(-1);
      }
      p++;
    }
    rez += minus * (a / nr);
  }
  return rez;
}
 
int main(){
  FILE *in = fopen("pinex.in", "r");
  FILE *out = fopen("pinex.out", "w");
  ciur(1000000);
  
  int n;
  long long a, b;
  fscanf(in, "%d", &n);
  for(int i=0;i<n;i++)
  {
    fscanf(in, "%lld%lld", &a, &b);
    fprintf(out, "%lld\n", a - diviz(a, b));
  }
}