#include <cstdio>
#include <cstring>

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

#define Max 1000000 //10^6

long long A,B;
int nrp,nrd;
int d[Max];
int prim[Max];
int p[Max];
int 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("%d", &T);
	
	while(T--)
	{
		scanf("%lld %lld\n", &A, &B);
		nrd=0;
		long long prod=1;
		long long  xx=0;
		//afla divizorii primi ai lui B
		for (i=1;i<=nrp && p[i]<=B;++i)
			 if (B%p[i]==0)
			 {
				 d[++nrd]=p[i];
				 prod*=p[i];
				 xx+=A/p[i];
			 }
			 
		//for (i=1;i<=nrd;++i) printf("%d ", d[i]);
	    //printf("\n");
		if (nrd==1)
		{
            x=A/d[1];
			printf("%lld\n", A-x);
		}
		else
		if (nrd==2)
		{
			x=A/d[1]+A/d[2]-A/(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+=A/(d[i]*d[j]);
			//printf("%d %d %d\n", xx,xxx,A/prod); 	
            printf("%lld\n", A-(xx-xxx+A/prod));				 
		}
    }

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