#include <iostream>
#include <vector>
using namespace std;
vector<long long> v;
long long p, a, b;
void pf(long long nr)
{
	if (nr % 2 == 0)
		v.push_back(2);
	while (nr % 2 == 0)
		nr /= 2;
	for (long long i = 3; i * i <= b; i+=2)
	{
		if (nr % i == 0)
			v.push_back(i);
		while (nr % i == 0)
			nr /= i;
	}
	if (nr >= 3)
		v.push_back(nr);
}

int main()
{
	cin >> p;
	for (int i = 1; i <= p; i++)
	{
		v.clear();
		cin >> a >> b;
		pf(b);
		long long ans=0;
		for (int j = 0; j < v.size(); j++)
		{
			ans += (a / v[j]);
		}
		for (int j = 0; j < v.size() - 1; j++)
		{
			for (int l = j + 1; l < v.size(); l++)
			{
				ans -= (a - v[j] * v[l]);
			}
		}
		for (int j = 0; j < v.size() - 2; j++)
		{
			for (int l = j + 1; l < v.size()-1; l++)
			{
				for (int x = l + 1; x < v.size(); x++)
				{
					ans -= (a - v[j] * v[l]*v[x]);
				}
				
			}
		}
		cout << a-ans << "\n";
	}
	return 0;
}