#include <cstdio>
#include <cstring>

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


#define pmax 1000000
#define nmax 101000

int t;
long long A,B,b,sol=0,prod;
int viz[pmax];
int q[100];
int p[nmax];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &t);
}

void solve()
{
	int i,j,nrr,nrd=0,nr;
	for (i=2;i<=pmax;++i)
		 if (!viz[i])
		 {
			 p[++nrd]=i;
			 for (j=i+i;j<=pmax;j+=i)
				  viz[j]=1;
		 }
		 
	while(t--)
	{
		scanf("%lld %lld", &A, &B);
		
		b=B;
		nr=0;
		for (i=1;1LL*p[i]*p[i]<=b;++i)
		{
			if(b%p[i]==0)
			{
				q[++nr]=p[i];
				while(b%p[i]==0)
					b/=p[i];
			}
		}
		sol=0;
		if (b>1)
			 q[++nr]=b;
		
		for (i=1;i<(1<<nr);++i)
		{
			prod=1;
			nrr=0;
			for (j=1;j<=nr;++j)
				 if (i&(1<<(j-1)))
				 {
					nrr++;
                    prod*=q[j];
				 }
			if (nrr&1)
                sol+=A/prod;
            else
                sol-=A/prod;
		}

		printf("%lld\n", A-sol);
	}
	
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}