# include <stdio.h>
# include <cstring>
int c[1000000],p[1000005],x,i,s,j,k,m,n;
bool viz[1000005];
long long a,b;
void submultimi()
{
	int i,q=1;
	for (i=1; i<=m; i++)
		q=q*2;
	long long suma=0;
	for (i=1; i<=q-1; i++)
	{
		long long prod=1;
		long long x=i;
		int nr=m;
		int nr1=0;
		while (x!=0)
		{
			if (x%2==1) {prod=prod*c[m-nr+1]; nr1++;} 
			nr--;
			x/=2;
		}
		if (nr1%2==1)
			suma+=a/prod;
		else
			suma-=a/prod;
	}
	printf("%lld\n",a-suma);
}
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%d\n",&n);
	k=0;
	p[++k]=2;
	for (i=3; i<=1000005; i+=2)
		if (viz[i]==false)
		{
			p[++k]=i;
			for (j=3*i; j<=1000005; j+=2*i)
				viz[j]=true;
		}
	for (s=1; s<=n; s++)
	{
		scanf("%lld %lld\n",&a,&b);
		m=0;
		memset(c,0,sizeof(c));
		x=b; i=1;
		while (x!=1)
		{
			if (x%p[i]==0)
			{
				c[++m]=p[i];
				while (x%p[i]==0) x/=p[i];
			}
			i++;
		}
		submultimi();
	}
}