#include<stdio.h>
int a,b,s,S,d[30],np[100001],i,n,k,m,nr,x[30],t;
bool v[1000001];

void nrdiv()
{	int p,i;
	p=1;
	for(i=1; i<=n; ++i) p=p*d[x[i]];
	s=s+a/p;
}

void backtracking()
{	k=1; s=0;
	do
	{	while(x[k]<m-n+k)
		{	x[k]=x[k]+1;
			if(k==n) nrdiv(); 
		  else {++k; x[k]=x[k-1];}
		}
		--k;
	} while(k); 
	if(n%2) S=S+s; else S=S-s;
} 

void gennrprime()
{	int i,j;
	for(i=2; i<=1000000; ++i)
		if(!v[i])
		{	np[++nr]=i;
			for(j=i+i; j<=1000000; j+=i) v[j]=1;
		}
}

int main()
{	FILE *fin, *fout;
	fin = fopen ("pinex.in", "r");
	fout = fopen ("pinex.out", "w");
	
	fscanf (fin,"%d",&t);
	nr=0; gennrprime();
	for(;t;--t)  
	{	fscanf (fin,"%d%d",&a,&b);
		m=0; i=1;
    while(b>1 && np[i]*np[i]<=b)
	  {	if(!(b%np[i]))
		  {	d[++m]=np[i];
				while(!(b%np[i])) b=b/np[i];
		  }
		++i;
	  }
	if(b>1) d[++m]=b;
	S=0; 
	for(n=1; n<=m; ++n) backtracking();
	fprintf (fout,"%d\n",a-S);
	}
	fclose(fout); return 0;
}