#include <fstream>

using namespace std;

#define MAX_D 15
#define MAX_H 1000005

ifstream fin ("pinex.in");
ofstream fout ("pinex.out");

int T, B, D[MAX_D], N, Np, P[MAX_H];
long long A;

void ciur()
{
	char viz[MAX_H];
	memset(viz, 0, sizeof viz);

	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 solve()
{
	fin >> A >> B;

	N = 0;
	int b = B;
	for(int i = 1; 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;
	int M = (1 << N);

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

		for(int j = 0; j < N; ++j)
			if(i & (1 << j))
				l *= D[j+1],
				++ nrb;

		if(nrb & 1)
			Sol -= A/l;
		else
			Sol += A/l;
	}

	fout << Sol << "\n";
}

int main()
{
	fin >> T;

	ciur();
	while(T--)
		solve();
}