#include<math.h>
#include<stdio.h>
int f[21],viz[21];
long long d,a;
void calc()
{
int i,nr=0;
long long prod=1;
for(i=1;i<=f[0];i++)
 if(viz[i]==1)
  {
  nr++;
  prod=prod*f[i];
  }
if(nr%2==1)
 d=d+a/prod;
else
 d=d-a/prod;
}
void pinex(long long l)
{
int i;
for(i=l+1;i<=f[0];i++)
 if(viz[i]==0)
  {
  viz[i]=1;
  calc();
  pinex(i);
  viz[i]=0;
  }
}
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	int m,i,j;
	long long b,c,p;
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		for(j=0;j<=20;j++)
		{
			f[j]=0;
			viz[j]=0;
		}
		scanf("%lld%lld",&a,&b);
		if(b%2==0)
		{
			f[1]=2;
			f[0]=1;
			while(b%2==0)
			{
				b=b/2;
			}
		}
		c=sqrt(b);
		p=3;
		while(p<=c)
		{
			if(b%p==0)
			{
				f[++f[0]]=p;
				while(b%p==0)
			{
			b=b/p;
			}
			}
		p=p+2;
		}
		if(b>1)
			f[++f[0]]=b;
		d=0;
		pinex(0);
		printf("%lld\n",a-d);
	}
return 0;
}