#include <fstream>
#include <bitset>
#include <vector>
using namespace std;

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

using llong = long long;
const int EMax = 5 + 1e6;

bitset<EMax> e;
vector<llong> p, d;

void getDiv(llong x, vector<llong>& div);
void eratostene();

llong a, b, sol;
int q;

int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(nullptr);
	fout.tie(nullptr);

	eratostene();
	fin >> q;
	while (q--)
	{
		fin >> a >> b;
		sol = 0;

		getDiv(b, d);
		for (llong i = 1; i < (1LL << d.size()); ++i)
		{
			llong nr = 1, bits = 0;
			for (llong j = 0; j < d.size(); ++j)
				if (i & (1LL << j))
					++bits, nr *= d[j];

			if (bits % 2 == 0) 	sol -= (a / nr);
			else 				sol += (a / nr);
		}

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

	fin.close();
	fout.close();
}

void getDiv(llong x, vector<llong>& div)
{
	div.clear();
	for (const auto& pr : p)
	{
		if (pr * pr > x) continue;

		if (pr <= x && x % pr == 0) div.push_back(pr);
		while (x % pr == 0) x /= pr;
	}
	if (x > 1) div.push_back(x);
}

void eratostene()
{
	e[0] = e[1] = true;
	for (llong i = 2; i < EMax; ++i)
		if (!e[i]) for (llong j = 2; i * j < EMax; ++j)
					e[i * j] = true;
	p.push_back(2);
	for (int i = 3; i < EMax; i += 2)
		if (!e[i]) p.push_back(i);
}