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

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

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

	for(i = 1; i <= 500000; i++)
        if(!pr[i])
            pr2[++nrpr]=2*i+1;
}

void factori()
{
	i=-1;
	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 && (long long)pr2[i] * pr2[i] > B)
		{
			fact[++nrf]=B;
			B=1;
		}
	}
}

void rez()
{
	int nrs=(1<<nrf)-1, nr;
	long long prod;
	for(i=1;i<=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("%d\n",&M);
	for(id=1;id<=M;id++)
	{
		scanf("%lld %lld",&A,&B);

		R=0;
		factori();
		rez();

		printf("%lld\n",(long long)A-R);
	}
}