#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

const int MAX = 1000010;
const int DIM = 78510;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int t;
vector <int> v;
bitset <MAX> viz;
int st[10], dim;
int ciur[DIM];
long long ans = 0;
long long x, y;

void Solution()
{
	long long aux = 1;
	int cnt = 0;
	for (int i = 1;i <= dim;++i)
	{
		if (st[i])
		{
			++cnt;
			aux *= v[i - 1];
		}
	}
	if (aux > x || cnt == 0)
		return;
	if (cnt % 2)
		ans += x / aux;
	else
		ans -= x / aux;
}

void Ciur()
{
	ciur[++ciur[0]] = 2;
	for (int i = 3;i * i < MAX;i += 2)
		if (viz[i] == 0)
			for (int j = i * i;j < MAX;j += 2 * i)
				viz[j] = 1;
	for (int i = 3;i < MAX;i += 2)
		if (viz[i] == 0)
			ciur[++ciur[0]] = i;
}

void Back(int k)
{
	if (k > dim)
	{
		Solution();
		return;
	}
	st[k] = 0;
	Back(k + 1);
	st[k] = 1;
	Back(k + 1);
}

long long Solve()
{
	int cnt = 0;
	v.clear();
	ans = 0;
	for (int i = 1;ciur[i] * ciur[i] <= y;++i)
	{
		if (y % ciur[i] == 0)
		{
			v.push_back(ciur[i]);
			while (y % ciur[i] == 0)
				y /= ciur[i];
		}
	}
	if (y != 1)
		v.push_back(y);
	dim = (int)v.size();
	Back(1);
	return x - ans;
}

int main()
{
	Ciur();
	fin >> t;
	for (int i = 1;i <= t;++i)
	{
		fin >> x >> y;
		fout << Solve() << "\n";
	}
	fin.close();
	fout.close();
	return 0;
}