#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()
{
long long i, j; 
for (i = 3; i <= 1000000; i = i + 2) 
{
    if (ciur[i >> 4] & (1 << ((i >> 1) & 7))) continue;

      for (j = i + i + i; j <= ; j = j + (i<<1))
            ciur[j >> 4] = ciur[j >> 4]| 1 << ((j >> 1) & 7);
prime[++prime[0]]=2;

for (i = 1; (i<<1) + 1 <= 1000000; i++)
	if ((ciur[i >> 3] & (1 << (i & 7))) == 0)
                prime[++prime[0]]=(i<<1)+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; 
}