#include <cstdio>
#include <cstring>
#include <cmath>

#define file_in "pinex.in"
#define file_out "pinex.out"

#define Max 1000000 //10^6

long long A,B;
long long nrp,nrd;
long long d[Max];
long long prim[Max];
long long p[Max];
long long T,x;

int main()
{
	int i,j;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	//ciur
	for (i=2;i<=Max;++i)
		 if (!prim[i])
		 {
			 p[++nrp]=i;
			 for (j=i+i;j<=Max;j+=i)
				  prim[j]=1;
		 }
	
	scanf("%lld", &T);
	
	while(T--)
	{
		scanf("%lld %lld\n", &A, &B);
		
		if (B==1) printf("%lld\n", A);
		else
		{
		
		nrd=0;
		long long prod=1;
		long long  xx=0;
		//afla divizorii primi ai lui B
		i=0;
		while(B>1)
		{
			i++;
			 if (B%p[i]==0)
			 {
				 d[++nrd]=p[i];
				 prod*=p[i];
				 xx+=A/p[i];
				 while (B%p[i]==0) B/=p[i]; 
			 }
			 
			 if (p[i]>sqrt(B) && B>1) 
			 {
                d[++nrd]=B;
                B=1;
			 }
		}
			 
			 
		//for (i=1;i<=nrd;++i) printf("%d ", d[i]);
	    //printf("\n");
		if (nrd==1)
		{
            x=(long long)A/d[1];
			printf("%lld\n", A-x);
		}
		else
		if (nrd==2)
		{
			x=(long long)A/d[1]+(long long)A/d[2]-(long long)A/(1LL*d[1]*d[2]);
			printf("%lld\n", A-x);
		}
		else
		{
			long long xxx=0;
			for (i=1;i<=nrd;++i)
				 for (j=i+1;j<=nrd;++j)
					  xxx+=(long long)A/(1LL*d[i]*d[j]);
			//printf("%d %d %d\n", xx,xxx,A/prod); 	
            printf("%lld\n", A-(long long)(xx-xxx+A/prod));				 
		}
		}
    }

	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}