#include<stdio.h>
#include<math.h>
long long a;
long long b;
bool c[1000001];
long p[800001];
long e[800001];    
void desc ()
{
	long lim,d,ex=0,num=1,n,ns,v,bi,w=0,nb,i;
	long long prod=1,s=0;
	lim=sqrt(b);
	n=b;
	d=2;num=1;
	while (d<=lim && b>1)
	{
		ex=0;
		while (b%d==0)
		{
			b=b/d;
			ex++;
		}
		if (ex)
			e[++w]=d;
		num++;
		d=p[num];
	}
	if (b>1)
		e[++w]=b;
	ns=(1<<w)-1;
	for (v=1;v<=ns;v++)
		{
			prod=1;nb=0;
			for (bi=0;bi<w;bi++)
				if (v&(1<<bi))
				{
					prod=(long long)prod*e[w-bi];
					nb++;
				}
			if (nb&1)
				s=(long long)s+a/prod;
			else
				s=(long long)s-a/prod;
		}
	printf("%lld\n",a-s);
}

void ciur()
{
	long i,j;
	c[1]=1;
	p[1]=2;
	p[0]=1;
	for (i=2;i<=1000000;i=i+2)
		c[i]=1;
	for (i=3;i*i<=1000000;i=i+2)
	{
		p[++p[0]]=i;
		for (j=i+i+i;j<=1000000;j=j+(i<<1))
			c[j]=1;
	}
}

int main()
{
	long m,i;
	
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	scanf("%ld",&m);
	ciur();
	for (i=1;i<=m;i++)
	{
		scanf("%lld%lld",&a,&b);
		desc();
	}	
	return 0;
}