#include <fstream>
#define lld long long
#define MAX 1000001
using namespace std;

lld a, b, nr, b1, p;
int m, pr[MAX], kp, mm[MAX], nm;
bool v[MAX], is_pos;

void prime()
{
	for (int i = 2; i <= MAX; i++)
	{
		if (!v[i])
		{
			pr[kp++] = i;
			for (int j = i << 1; j <= MAX; j += i)
				v[j] = 1;
		}
	}
}

void backprod(int k, int n, int nm, int lpos, lld p)
{
	if (k == n)
	{
		if (is_pos)
			nr += a / p;
		else nr -= a / p;
		return;
	}
	for (int i = lpos + 1; i < nm; i++)
		backprod(k + 1, n, nm, i, p * mm[i]);
}

lld pinex(lld a, lld b)
{
	nm = 0;
	nr = 0;
	b1 = b;
	p = 1;
	for (int i = 0; i < MAX && b1 != 1; i++)
	{
		if (b1 % pr[i] == 0)
		{
			mm[nm++] = pr[i];
			p *= pr[i];
			nr += a / pr[i];
			do
			{ 
				b1 /= pr[i];
			} while (b1 % pr[i] == 0);
		}
	}
	p = a / p;
	if (nm > 1)
	{
		if (nm % 2 == 0)
			nr -= p;
		else
			nr += p;
	}
	is_pos = 0;
	for (int k = 2; k < nm; k++, is_pos = !is_pos)
		backprod(0, k, nm, -1, 1);
	return nr;
}

int main()
{
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	prime();
	f >> m;
	for (; m; m--)
	{
		f >> a >> b;
		g << a - pinex(a, b) << "\n";
	}
	return 0;
}