#include <cstdio>
#define SQRT 1000000
#define LOG 100
char ciur[SQRT+1];
int prim[SQRT+1];
long long div[LOG+1];
int main(){
   FILE*fi,*fout;
   int i,j,n,m;
   fi=fopen("pinex.in" ,"r");
   fout=fopen("pinex.out" ,"w");
   fscanf(fi,"%d " ,&n);
   for(i=2;i*i<=SQRT;i++)
    if(ciur[i]==0)
     for(j=i*i;j<=SQRT;j+=i)
       ciur[j]=1;
   m=0;
   for(i=2;i<=SQRT;i++)
     if(ciur[i]==0)
       prim[++m]=i;
   for(i=1;i<=n;i++){
      long long a,b;
      fscanf(fi,"%lld %lld " ,&a,&b);
      int k=0;
      j=1;
      while(j<=m&&1LL*prim[j]*prim[j]<=b){
         int e=0;
         while(b%prim[j]==0){
            b/=prim[j];
            e++;
         }
         if(e>0)
           div[k++]=prim[j];
         j++;
      }
      if(b>1)
        div[k++]=b;
      long long ans=0;
      for(int conf=1;conf<(1<<k);conf++){
         long long prod=1;
         int cnt=0;
         for(j=0;j<k;j++)
            if(conf&(1<<j)){
              prod*=div[j];
              cnt++;
            }
         if(cnt&1)
           ans+=(a/prod);
         else
           ans-=(a/prod);
      }
      fprintf(fout,"%lld\n" ,a-ans);
   }
   fclose(fi);
   fclose(fout);
   return 0;
}