#include <stdio.h>
#define N 81430
#define M 1000005
int prim[N],vfp=-1;
char 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)
 {if(sieve[i]==0)
  for (j=i*i;j<=1000000;j+=i)
  {sieve[j]=1;
   op1++;
  }
 }
 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);
 long long int a,b,count,d;
 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;(long long)prim[j]*prim[j]<=b;j++)
  {if(b%prim[j]==0)
   {list[++vf]=prim[j];
    op2++;
   }
   while(b%prim[j]==0)b/=prim[j];
  }
  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++)
   {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;
}