#include <fstream>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long v[100001], A, B, M, cnt;

void divPrimi()
{
	cnt = 0;
	for(int d = 2; d * d <= B; ++d)
		if(B % d == 0)
		{
			v[++cnt] = d;
			do
			{
				B /= d;
			}
			while(B % d == 0);
		}
	if(B > 1)
		v[++cnt] = B;
}

void pinex()
{
	long long lim = (1 << cnt), k, mc, D = A;
	for(int i = 1; i < lim; ++i)
	{
		k = 0, mc = 1;
		for(int j = 0; (1 << j) <= i; ++j)
			if(i & (1 << j))
			{
				k++;
				mc *= v[j + 1];
			}
		if(k % 2 == 0) D += A / mc;
		else D -= A / mc;
	}
	g << D << '\n';
}

int main()
{
	f >> M;
	while(M--)
	{
		f >> A >> B;
		divPrimi();
		pinex();
	}
	f.close();
	g.close();
	return 0;
}