#include<stdio.h>
int p[2001];
long long  desc ( long long  nr ){
  long long f,pu,k1=-1;
  f=2;
  while(nr!=1){
    pu=0;
    while(nr%f==0){
      nr=nr/f;
      pu++;
    }
    if(pu!=0){
      k1++;
      p[k1]=f;
    }
    f++;
  }
  return k1+1;
}
int main(){
  long long  i,l,n,a,b,s,prod,nr,k,j;
  freopen("pinex.in","r",stdin);
  freopen("pinex.out","w",stdout);
  scanf("%lld",&n);
  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;
}