#include<cstdio>
#include<cstring>
#include<math.h>
#define LL long long
using namespace std;

bool ciur[1000010];
int prime[1000010];
LL T,x[100]; 

void fa_ciur()
{
	long i,j;
	ciur[1]=1;
	prime[1]=2;
	prime[0]=1;
	for (i=2;i<=1000010;i=i+2)
		ciur[i]=1;
	for (i=3;i<=1000010;i=i+2)
	{
		if (!ciur[i])
	{
		prime[++prime[0]]=i;
		for (j=i+i+i;j<=1000010;j=j+(i<<1))
			ciur[j]=1;
	}
	}

}


}
void desc(LL b)
{
	LL elf=1,lim=(LL)sqrt(b);
	x[0]=0;

	while(b>1 && prime[elf]<=lim)
	{
		if(b%prime[elf]==0)
		{
			x[++x[0]]=prime[elf];
			while(b%prime[elf]==0)
				b/=prime[elf];
		}
	elf++; 
	}
	if(b>1)
		x[++x[0]]=b;
}

void solve(int n,int k)
{
int prod,num,i,j,ns=(1<<n)-1;
T=0;
for(i=1;i<=ns;i++)
{
	prod=1; num=0;
	for(j=0;j<n;j++)
		if(i&(1<<j))
		{
			prod=prod*x[n-j];
			num++;
		}
	if(num&1)
		T=T+k/prod;
	else
		T=T-k/prod;
}
}

int main()
{
	LL a,b;
	int teste;
	
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	scanf("%d",&teste); 

	fa_ciur();
	
	while(teste--)
	{
		scanf("%lld%lld",&a,&b);
		desc(b);
		solve(x[0],a);
		printf("%lld\n",a-T);
	} 
	return 0; 
}