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

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

void fa_ciur()
{
	int i,j,lim=1000000;
	for(i=4;i<=lim;i+=2)
		ciur[i]=true; 
	prime[++prime[0]]=2; ciur[2]=false;
	for(i=3;i<=lim;i+=2)
		if(ciur[i]==false)
		{
			prime[++prime[0]]=i;
			for(j=i+i+i;j<=lim;j=i+(i<<1))
				ciur[j]=true;
		}
}
void desc(LL b)
{
	LL elf=1,d=ciur[elf],lim=(LL)sqrt(b);
	x[0]=0;

	while(b>1 && d<=lim)
	{
		if(b%d==0)
		{
			x[++x[0]]=d;
			while(b%d==0)
				b/=d;
		}
	elf++; d=ciur[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; 
}