#include <stdio.h>
int ciur[1000001],pr[1000000],st[36],sol[36],m;
long long a,b,prod,nr,j,i;
int back(int k)
{
	if (k==sol[0]+1)
		return 0;
	for (st[k]=st[k-1]+1;st[k]<=sol[0];st[k]++)
	{
		prod*=sol[st[k]];
		if (k%2==1) nr+=1LL*(a/prod);
		else nr-=(a/prod);
		back(k+1);
		prod/=sol[st[k]];
	}
	return 0;
}
int main(void)
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	pr[++pr[0]]=2;
	for (i=3;i<=1000000;i+=2)
	{
		if (!ciur[i])
		{
			pr[++pr[0]]=i;
			if (i*i>1000000) continue;
			for (j=i*i;j<=1000000;j+=i)
				ciur[j]=1;
		}
	}
	scanf("%d",&m);
	while (m--)
	{
		nr=0;
		scanf("%lld%lld",&a,&b);
		for (i=1;i<=pr[0] && pr[i]*pr[i]<=b;i++)
		{
			if (b%pr[i]==0)
			{
				sol[++sol[0]]=pr[i];
				while (b%pr[i]==0) b/=pr[i];
			}
		}
		if (b>1) sol[++sol[0]]=b;
		for (i=1;i<=sol[0];i++) st[i]=0;
		prod=1;
		back(1);
		printf("%lld\n",a-nr);
		sol[0]=0;
	}
	
	
}