#include<stdio.h>
using namespace std;
long long n1,nr,nr1,nr2,maxi,i,j,i10,t10,p,s,aux,n[502],m[502],a[1000002],pr[78499],d[102];
int main()
{
freopen("pinex.in","r",stdin);
freopen("pinex.out","w",stdout);
scanf("%lld",&t10);
for(i10=1;i10<=t10;i10++)
{
	scanf("%lld",&m[i10]);
	scanf("%lld",&n[i10]);
	if(n[i10]>maxi) maxi=n[i10];
}
for(i=1;i*i<=maxi;i++)
	;
maxi=i;
pr[1]=2;
nr=1;
for(i=3;i<=maxi&&i*i<=maxi;i=i+2)
	if(a[i]==0)
	{
		nr++;
		pr[nr]=i;
		for(j=i*i;j<=maxi;j=j+i)
			a[j]=1;
		if(i%6==1) i=i+2;
	}
for(i=i;i<=maxi;i=i+2)
	if(a[i]==0)
	{
		nr++;
		pr[nr]=i;
		if(i%6==2) i=i+2;
	}
for(i10=1;i10<=t10;i10++)
{
	aux=n[i10];
	nr1=0;
	for(i=1;i<=nr&&pr[i]*pr[i]<=aux;i++)
		if(aux%pr[i]==0)
		{
			while(aux%pr[i]==0)
				aux=aux/pr[i];
			nr1++;
			d[nr1]=pr[i];
		}
	if(aux!=1)
	{
		nr1++;
		d[nr1]=aux;
	}
	n1=((1<<nr1)-1);
	s=0;
	for(j=1;j<=n1;j++)
	{
		aux=j;
		nr2=0;
		while(aux>0)
		{
			aux=(aux&(aux-1));
			nr2++;
		}
		if(nr2%2==1)
		{
			p=1;
			for(i=0;i<=nr1;i++)
				if((j&(1<<i))>0) p=p*d[i+1];
			s=s+m[i10]/p;
		}
		else
		{
			p=1;
			for(i=0;i<=nr1;i++)
				if((j&(1<<i))>0) p=p*d[i+1];
			s=s-m[i10]/p;
		}
	}
	printf("%lld\n",m[i10]-s);
}
return 0;
}