#include <cstdio>
#include <bitset>
using namespace std;
#define ll long long
#define L 1000000

bitset< 500000 > e;
int p[78500];

inline void ciur()
{
	p[0]=1;
	p[1]=2;
	for(int i=3; i*i<L; ++i,++i)
	{
		if(e[i>>1]==1)
			continue;
		for(int j=i*i,i1=(i<<1); j<L; j+=i1)
			e[j>>1]=1;
	}

	for(int i=3; i<L; ++i,++i)
	{
		if(e[i>>1]==0)
			p[++p[0]]=i;
	}
}

inline void rezolva()
{
	ll A,B;
	ll pr[20]={0};
	scanf("%lld%lld",&A,&B);
	if((B&1)==0)
	{
		pr[0]=1;
		pr[1]=2;
		while((B&1)==0)
			B>>=1;
	}

	for(int i=2; i<=p[0] && B!=1 && p[i]*p[i]<=B; ++i)
	{
		if(B%p[i]==0)
		{
			pr[++pr[0]]=p[i];
			while(B%p[i]==0)
				B/=p[i];
		}
	}
	if(B!=1)
		pr[++pr[0]]=B;
	int lim=(1<<((int)pr[0]));
	ll r=A;
	int cnt;
	ll x;
	for(int i=1; i<lim; ++i)
	{
		cnt=0;
		x=1;
		for(int j=i,t=1; j; j>>=1,++t)
		{
			if((j&1)==0)
				continue;
			++cnt;
			x*=pr[t];
		}

		if((cnt&1))
			r-=A/x;
		else
			r+=A/x;
	}

	printf("%lld\n",r);
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);

	ciur();
	int M;
	scanf("%d",&M);
	for(; M; --M)
		rezolva();

	return 0;
}