#include<stdio.h>
#define prmax 1000000
#define nrpmax 100000
int nr,nrd;
long long a,b,sol;
bool ciur[prmax];
int prim[nrpmax],divp[16];

void gene()
{
	int i,j;
	prim[nr=1]=2;
	for(i=4;i<=prmax;i+=2)
		ciur[i]=1;
	for(i=3;i<=prmax;i++)
		if(!ciur[i])
		{
			prim[++nr]=i;
			if(i>1000)
				continue;
			for(j=i*i;j<=prmax;j=j+i+i)
				ciur[j]=1;
		}
}

void div_b()
{
	int div=1,nr;
	nrd=0;
	while(b>1 && (long long)prim[div]*prim[div]<=b)
	{
		nr=0;
		while(b%prim[div]==0)
		{
			nr++;
			b=b/prim[div];
		}
		if(nr)
			divp[++nrd]=prim[div];
		div++;
	}
	if(b>1)
		divp[++nrd]=b;
}

int nr_bit(int x)
{
	int nr=0;
	while(x)
	{
		nr++;
		x=x&(x-1);
	}
	return nr;
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	gene();
	int t,i,j,lim;
	long long prod;
	scanf("%d",&t);
	while(t--)
	{
		sol=0;
		scanf("%lld%lld",&a,&b);
		div_b();
		lim=1<<nrd;
		for(i=0;i<lim;i++)
		{
			nr=nr_bit(i);
			prod=(nr&1)?-1:1;
			for(j=0;j<nrd;j++)
				if(i&(1<<j))
					prod=prod*divp[j+1];
			sol=sol+a/prod;
		}
		printf("%lld\n",sol);
	}
	return 0;
}