#include<stdio.h>
int p[2001],ciur[1000001],prime[100001],pr;
long long  desc ( long long  nr ){
  long long i,pu,k1=-1;
  for(i=1;prime[i]*prime[i]<=nr;i++){
    pu=0;
    while(nr%prime[i]==0){
      pu++;
      nr=nr/prime[i];
    }
    if(pu!=0){
      k1++;
      p[k1]=prime[i];
    }
  }
  if(nr!=1){
    k1++;
    p[k1]=nr;
  }
  return k1+1;
}
int main(){
  long long  i,l,n,a,b,s,pi,prod,nr,k,j,m,up;
  freopen("pinex.in","r",stdin);
  freopen("pinex.out","w",stdout);
  scanf("%lld",&n);
  pi=2;
  up=1000;
  while(pi<=up){
    for(m=2;m<=1000000/pi;m++)
      ciur[pi*m]=1;
    pi++;
    while(ciur[pi]==1)
      pi++;
  }
  for(i=2;i<=1000000;i++)
      if(ciur[i]==0){
        pr++;
        prime[pr]=i;
      }
  for(l=1;l<=n;l++){
    scanf("%lld%lld",&a,&b);
    k=desc(b);
    s=0;
    for(i=0;i<(1<<k);i++){
      // calc prod fact primi coresp lui i;
      prod=1;
      nr=0;
      for(j=0;j<k;j++)
        if(i&(1<<j)){
          prod*=p[j];
          nr++;
        }
      if(nr%2==0)
        s+=a/prod;
      else
        s-=a/prod;
    }
    printf("%lld\n",s);
  }
  return 0;
}