#include<fstream.h>
ifstream f("pinex.in"); ofstream g("pinex.out");
char w[1000011]; //w[i] == 0 daca i este prim
long long a,b,sum,s,d[30],p[100001],pr;
int T,n,i,k,nr=0,m,x[30],vf,mk[31],nb1,j;
void ciur()
{int i,j;
 for(i=2; i<=1000000; i++)
  if(!w[i])
   {p[++nr]=i;
	for(j=i+i; j<=1000000; j+=i) w[j]=1;
   };
 for(i=1;i<=30;i++) mk[i]=1<<(i-1);
}
void prelsol()
{int i; long long pr=1;
 for(i=1; i<=n; i++) pr=pr*d[x[i]];
 s+=a/pr;
}

int main()
{ciur();
 f>>T;
 while(T)  
   {f>>a>>b;
	m=0; i=1;
    while(b>1 && p[i]*p[i]<=b)
	  {if(b%p[i]==0)
		  {d[++m]=p[i];
		   while(b%p[i]==0) b/=p[i];
		  };
		i++;
	  }
	if(b>1) d[++m]=b;
	sum=0; 
	vf=1<<m;
	for(i=1;i<vf;i++) 
		{
		 pr=a; nb1=0;
		 for(j=1;j<=m;j++) if(i & mk[j]) { pr/=d[j]; nb1++;}
		 if(nb1%2) sum+=pr; else sum-=pr;
		}
	g<<a-sum<<'\n';  
	T--;
   }
 g.close(); return 0;
}