#include <cstdio>
#include <fstream>

using namespace std;

FILE *f,*s;

int T, D[50], N, Np, P[1000005];
long long A, B;

void Ciur()
{
	char viz[1000005];
	
	for(int i=1;i<=1000005;i++) viz[i]=0;

	int H = 1000000;
	
	for(int i = 2; i <= H; ++i)
	{	
		if(viz[i] == 0)
		{
			P[++Np] = i;

			for(int j = i+i; j <= H; j += i)
				viz[j] = 1;
		}
	}	
}

void Calculeaza()
{
	fscanf(f,"%d %d",&A,&B);
	
	N = 0;
	
	long long b = B;
	
	for(int i = 1; 1LL * P[i]*P[i] <= b; ++i)
	{
		if(B % P[i] == 0)
		{
			D[++N] = P[i];
			while(B % P[i] == 0)
				B /= P[i];
		}
	}
	
	if(B > 1)
		D[++N] = B;

	long long Sol = A, M = (1LL << N);

	for(int i = 1; i < M; ++i)
	{
		long long l = 1, nrb = 0;

		for(int j = 0; j < N; ++j)
		{	
			if(i & (1 << j))
				l *= D[j+1],
				++ nrb;
		}
		
		if(nrb & 1)
			Sol -= 1LL * A/l;
		else
			Sol += 1LL * A/l;
	}

	fprintf(s,"%lld\n",Sol);
}

int main()
{
	f=fopen("pinex.in","r");
	s=fopen("pinex.out","w");
	
	fscanf(f,"%d",&T);
	
	Ciur();
	
	while(T)
	{	
		Calculeaza();
		
		T--;
	}	
}