#include <fstream>

using namespace std;

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

void Pregen();
void Read();
void Solve();
void Fact();

long long m, a, b;
int prim[200], lp;
bool s[1000000];
long long fac[25], sf, res;

int main()
{
	Pregen();
	Read();
}

void Pregen()
{
	prim[++lp] = 2;
	for (int i = 3; i * i <= 1000000; i += 2)
		if (s[i] == false)
		{
			prim[++lp] = i;
			for (int j = i * i; j <= 1000000; j += 2 * i)
				s[j] = true;
		}
}

void Read()
{
	fin >> m;
	while (m-- != 0)
	{
		fin >> a >> b;
		Solve();
	}
}

void Solve()
{
	res = 0, sf = 0;
	Fact();

	long long prod;
	for (int i = 1; i < (1 << sf); ++i)
	{
		prod = 1;
		for (int j = 0; j < sf; ++j)
			if (((1 << j) & i) != 0)
				prod *= fac[j + 1];
		long long n1s = 0, aux = i, what = a / prod;
		while (aux)
		{
			++n1s;
			aux &= aux - 1;
		}
		if (n1s % 2 == 1)
			res += what;
		else
			res -= what;
	}

	fout << a - res << '\n';
}

void Fact()
{
	for (int i = 1; i <= lp; ++i)
		if (b % prim[i] == 0)
		{
			fac[++sf] = prim[i];
			while (b % prim[i] == 0)
				b /= prim[i];
		}
}