#include <stdio.h>
#define N 81430
#define M 1000005
int prim[N],vfp=-1;
int sieve[M];
//long long int op1=0,op2=0,op3=0,op4=0;

void genSieve()
{int i,j;
 vfp=-1;
 prim[++vfp]=2;
 for (int i=3;i<=1000;i+=2)
 {//op1++;
  if(sieve[i]==0)
  for (j=i*i;j<=1000000;j+=i)
  {sieve[j]=1;
   //op1++;
  }
 }
 for (i=4;i<=1000000;i+=2)sieve[i]=1;
 for (i=3;i<=1000000;i+=2)
 {if(!sieve[i])
   prim[++vfp]=i;
   //op1++;
 }
}

int list[100],vf=-1;
int main ()
{freopen("pinex.in","r",stdin);
 freopen("pinex.out","w",stdout);
 freopen("error.txt","w",stderr);
 long long int a,b,count,d,exp;
 int i,j,k,l,c,n,z;

 genSieve();
 scanf("%d",&n);
 for (int i=1;i<=n;i++)
 {scanf("%lld %lld",&a,&b);
  vf=-1;
  count=0;



  for (j=0;j<=vfp;j++)
  {//op2++;
   if(b%prim[j]==0)
   {list[++vf]=prim[j];
    do
    {b/=prim[j];}
    while(b%prim[j]==0);
    //if((long long)prim[j]*prim[j]>b)break;
   }

   if((j&63)==0)
   {if((long long)prim[j]*prim[j]>b)break;
   }
  }
  if(b>1)
  {list[++vf]=b;
  }
  z=1<<(vf+1);
  
  for (j=1;j<z;j++)
  {for (c=0,d=1,k=1,l=0;k<z;k<<=1,l++)
   {//op3++;
    if(j&k)
    {c++;
     d*=list[l];
   //  op3++;
    }
   }
   count+=(c&1)?a/d:-a/d;
 //  op4++;
  }
  printf("%lld\n",a-count);
 }
// printf("\n\n%lld %lld %lld %lld",op1,op2,op3,op4);
 
 return 0;
}