#include<stdio.h>
#include<iomanip.h>
int st[80000],m,k;
long long a,b,n,i,j,rez;
long long p[80000],nr,f[50000],num;
bool c[1000001];

void ciur()
{	nr=1;
	p[nr]=2;
	for (i=4;i<=1000001;i=i+2)
		c[i]=1;
	for(i=3;i<=1000001;i=i+2)
	if (!c[i]){
		p[++nr]=i;
		for(j=3*i;j<=1000001;j=j+2*i)
			c[j]=1;
	}
	
}

void descompunere()
{
	int e,l=1;
	num=0;
	do{

		e=0;
		if (b%p[l]==0)
			{
				f[++num]=p[l];
				do{ b=b/p[l];}while(b%p[l]==0);
		}
		else
			l++;
	}while(b!=1);
}

void init()
{ st[k]=-1;}

int succesor()
{
	if (st[k]<1) {st[k]++;return 1;}
		return 0;
}

int valid()
{return 1;}

int solutie()
{
	return k==num;
}

void excl()
{
	long n1=0;
	long long prod=1;
	long l;
	for (l=1;l<=num;++l)
		if (st[l])
			{n1++;
		prod=prod*f[l];}
			if (n1!=0)
		if (n1%2==0)
			n=n-(a/prod);
		else
			n=n+(a/prod);
}

void bkt()
{
	int as;
	k=1;
	init();
	while(k>=1)
	{
		do{}while((as=succesor())&&!valid());
		if (as) if (solutie()) excl();
		else
		{k++; init();}
		else
			k--;
	}
	
}

void prelucrare()
{
	num=0;
	nr=0;
	n=0;
	descompunere();
	bkt();
	rez=a-n;
	printf("%lld\n",rez);
	
	
}
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	ciur();
	scanf("%d",&m);
	for(i=1;i<=m;++i)
	{	scanf("%lld %lld",&a,&b);
	prelucrare();}
	
}