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

LL T,x[100]; 

void desc(LL b)
{
	LL d=3,lim=(LL)sqrt(b);
	memset(x,0,sizeof(x));
	if(!(b&1))
	{
		x[++x[0]]=2;
		while(!(b&1))
			b=b>>1;
	}
	while(b>1 && d<=lim)
	{
		if(b%d==0)
		{
			x[++x[0]]=d;
			while(b%d==0)
				b/=d;
		}
		d+=2;
	}
	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);
	while(teste--)
	{
		scanf("%lld%lld",&a,&b);
		desc(b);
		solve(x[0],a);
		printf("%lld\n",a-T);
	}
	return 0; 
}