#include <stdio.h>

FILE *f,*s;

long long int i,j,m;

bool v1[1000005],v4[1000005];

long long int v2[1000005],v3[1000005];

long long int rez;

long long int a,b;

void Back(long long int k)
{
	if(k==v3[0]+1)
	{
		long long int l=1;
		
		for(int i=1;i<=v3[0];i++)
			if(v4[i]>0) l*=v3[i];
		
		if(l!=1)
			rez+=(a/l);
	}	
	else
	{
		v4[k]=1; Back(k+1);
		v4[k]=0; Back(k+1);
	}		
	
}

int main()
{
	f=fopen("pinex.in","r");
	s=fopen("pinex.out","w");
	
	fscanf(f,"%lld",&m);
	
	v2[++v2[0]]=2;
	
	for(i=3;i<=1000000;i+=2)
	{
		if(!v1[i])
		{
			v2[++v2[0]]=i;
			
			for(j=i+i;j<=1000000;j+=i)
				v1[j]=1;
		}						
	}
	
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%lld %lld",&a,&b);
		
		long long int c=b;
		
		v3[0]=0;
		
		for(j=1;v2[j]*v2[j]<=c;j++)
		{
			if(c%v2[j]==0)
			{
				v3[++v3[0]]=-v2[j];
			
				while(c%v2[j]==0)
					c/=v2[j];
			}	
		}
		
		if(c>1) v3[++v3[0]]=-c;
			
		rez=0;
		
		Back(1);
		
		fprintf(s,"%lld\n",rez+a);	
	}
		
	fclose(s);
	
	return 0;
}