#include <bits/stdc++.h>

using namespace std;

vector <int> ciur;
vector <int> prime;
bitset <1000005> viz;
long long ans = 0;
void solve (long long a)
{
	int sz = prime.size();
	for (int masca = 1; masca < (1<<sz); ++masca)
	{
		int cate = 0;
		long long produs = 1;
		for (int i = 0; i<sz; ++i)
		{
			if ((1<<i)&masca)
			{
				++cate;
				produs *= prime[i];
			}
		}
		// cout << ans << "\n\n\n\n";
		if (cate%2)
			ans += a/produs;
		else ans -= a/produs;
	}
}
void ciurulet ()
{
	for (int i = 2; i<=1000000; ++i)
		if (viz[i] == 0)
		{
			ciur.push_back(i);
			for (int j = i+i; j<=1000000; ++j)
				viz[j] = 1;
		}
}
int main(int argc, char const *argv[])
{
	ifstream fin ("pinex.in");
	ofstream fout ("pinex.out");
	long long a, b;
	int m;
	ciurulet ();
	fin >> m;
	while (m--)
	{
		fin >> a >> b;
		prime.clear();
		ans = 0;
		for (auto x:ciur)
		{
			if (b%x == 0)
			{
				prime.push_back(x);
				while (b%x == 0)
					b/=x;
			}
		}
		if (b > 1)
			prime.push_back(b);
		// for (auto x:prime)
		// 	cout << x << " ";
		// cout << '\n';
		solve(a);
		fout << a - ans << '\n';
	}
	return 0;
}