#include<fstream>
using namespace std;
long long i,j,np,d,a,b,bc,s,z,n,p[1100000],D[100000];
int main()
{ifstream q("pinex.in");
ofstream w("pinex.out");
q>>n;
for(i=2;i<=1000;i++)
  if(!p[i])
   {p[++np]=i;
   for(j=i*i;j<=1000000;j+=i)
	 p[j]=1;}
	for(i=1001;i<=1000000;i++)
      if(!p[i])
	   p[++np]=i;
D[0]=1;
for(;n;n--)
  {q>>a>>b;
  d=1;
  bc=b;
  for(i=1;i<=np;i++)
	{if(p[i]*p[i]>bc)
	  break;
	if(bc%p[i]==0)
     {z=p[i];
     while(bc%z==0)
        bc/=z;z=-z;
    for(j=0;j<d;j++)D[j+d]=z*D[j];
      d*=2;}}
  if(bc>1)
   {z=-bc;
	for(j=0;j<d;j++)D[j+d]=z*D[j];
	  d*=2;}
  s=0;
  for(i=0;i<d;i++)
	s+=a/D[i];
  w<<s<<"\n";}
return 0;}