#include <stdio.h>
#include <math.h>

long long id,i,j,M,A,B,R;
bool pr[500005];
int pr2[500005],fact[1000],nrpr,nrf;


void ciur()
{
	pr2[0]=2; nrpr=0;
	for(i=1;i<=500000;i++)
	{
		if(!pr[i])
		{
			pr2[++nrpr]=2*i+1;
			for(j=2*i*i+2*i;j<=500000;j+=2*i+1)
				pr[j]=true;
		}
	}
}

void factori()
{
	i=-1; double L=sqrt(B); nrf=0;
	while(B>1)
	{
		i++;
		if(B%pr2[i]==0)
		{
			fact[++nrf]=pr2[i];
			while(B%pr2[i]==0)
				B/=pr2[i];
		}
		if(B>1 && pr2[i]>L)
		{
			fact[++nrf]=B;
			B=1;
		}
	}
}

void rez()
{
	int nrs=(1<<nrf)-1, nr;
	long long prod;
	for(i=1;i<=(long long)nrs;i++)
	{
		prod=1; nr=0;
		for(j=0;j<nrf;j++)
			if(i&(1<<j))
			{
				prod=prod*(long long)fact[nrf-j];
				nr++;
			}
		if(nr&1)
			R+=(long long)A/prod;
		else
			R-=(long long)A/prod;
	}
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	ciur();
	scanf("%lld",&M);
	for(id=1;id<=M;id++)
	{
		scanf("%lld %lld",&A,&B);
		R=0;
		factori();
		rez();
		printf("%lld\n",(long long)A-R);
	}
	
	
}