#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,s=0,n,ns,v,bi,w=0,prod=1,nb,i;
	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=prod*e[w-bi];
					nb++;
				}
			if (nb&1)
				s=s+a/prod;
			else
				s=s-a/prod;
		}
	printf("%ld\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<=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("%I64d%I64d",&a,&b);
		desc();
	}	
	return 0;
}