#include <cstdio>
#include <cstring>
#define SQRTB 1000004
using namespace std;
long long f[30],p[100000];
bool prim[SQRTB];
int nrd;

void prime()
{
	memset(prim,0,sizeof(prim));
	p[1]=2; int np=1, i,j;
	for (i=3;i<SQRTB;i+=2)
	 if (!prim[i])
		{
			p[++np]=i;
			for (j=i+i+i;j<SQRTB;j+=i)
			 prim[j]=1;
		}
}

void diviz(long long B)
{  nrd=0; int d;
	for (d=1; B>1; ++d)		
	{
		if (!(B%p[d]))
			{
			 f[++nrd]=p[d]; 
			 while (!(B%p[d])) B/=p[d];			 
			}
		if (p[d]*p[d]>B && B>1) { f[++nrd]=B; B=1;}
	}	
}

int main()
{
	prime();
	
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	int n,T,k,i; long long A,B;
	scanf("%d\n",&n);
	for (T=0;T<n;++T)
	{
		scanf("%lld %lld",&A,&B);
		diviz(B);		
		
		long long sol=A;
		for (k=1;(1<<nrd)>k;++k)
		{
		  long long prod=1; int ne=0;
		  for (i=0; i<=nrd; ++i)
		   if (k&(1<<i)) 
		      {++ne;
			   prod*=f[i+1];
			  }
		  prod=A/prod;
		  if (ne%2) prod*=(-1);
		  sol+=prod;
		}
		
		printf("%lld\n",sol);
	}
	
	return 0;
}