#include <stdio.h>
#define LMax 1000010
#define NMax 1000

typedef long long ll;
const char IN[]="pinex.in",OUT[]="pinex.out";

int Tes;
ll A,B,Rez;
int p[LMax] , pr[NMax];
bool b[LMax];

void ciur(){
	int i,j;
	for (i=2;i<LMax;++i) if (!b[i])
	{
		p[++p[0]]=i;
		if (i<=1000) for (j=i*i;j<LMax;j+=i)
			b[j]=true;
	}
}

void getpr(){
	int i;
	for (i=1;1LL*p[i]*p[i]<=B && i<=p[0];++i)
	{
		if (B%p[i]==0)
			pr[++pr[0]]=p[i];
	}
	if (pr[0]==1 && (B/p[1])%p[1]!=0) pr[++pr[0]]=B/p[1];
	if (!pr[0]) pr[++pr[0]]=B;
}

int main()
{
	int mask,i,ct;
	ciur();
	freopen(IN,"r",stdin);
	scanf("%d",&Tes);
	freopen(OUT,"w",stdout);
	while (Tes--)
	{
		scanf("%lld%lld",&A,&B);
		pr[0]=0;
		getpr();

		for (mask=1,ct=Rez=0;mask<(1<<pr[0]);++mask)
		{
			ll prod=1;ct=0;
			for (i=1;i<=pr[0];++i) if ((1<<i-1)&mask)
				prod*=pr[i],++ct;
			Rez+= (ct&1) ? A/prod : -A/prod;
		}
		printf("%lld\n",A-Rez);
	}
	fclose(stdout);
	fclose(stdin);
	return 0;
}