#define DM 1000001
#define DN 21
#include <bitset>
#include <cstring>
#include <fstream>
using namespace std;

ifstream fi ("pinex.in");
ofstream fo ("pinex.out");
bitset <DM/2+1> bs;
int prm[DM/2+1], dv[DN];
long long m, a, b, mltm, rez, aux, smn;

void ciur1()
{
	//Sar peste nr. pare
	//Merg cu j de la i*i
	for (int i = 3; i < DM; i += 2)
		if (!bs[i])
		{
			prm[++prm[0]] = i;
			for (long long j = 1LL*i*i; j < DM; j += (i << 1))
				bs[j] = 1;
		}
}

void ciur2()
{
	//Sar peste nr. pare
	//Memorez pentru 2*i+1
	for (int i = 1; (i << 1) + 1 < DM; ++i)
		if (!bs[i])
		{
			prm[++prm[0]] = (i << 1) + 1;
			for (long long j = i + i + i + 1; (j << 1) + 1 < DM; j += (i << 1) + 1)
				bs[j] = 1;
		}
}

void ciur3()
{
	//Sar peste nr. pare
	//Merg cu j de la i*i
	//Memorez pentru 2*i+1
	for (int i = 1; ((i*i) << 1) + (i << 1) < DM; ++i)
		if (!bs[i])
			for (int j = ((i*i) << 1) + (i << 1); (j << 1) + 1 < DM; j += (i << 1) + 1)
				bs[j] = 1;
	for (int i = 1; i < DM/2+1; ++i)
		if (!bs[i])
			prm[++prm[0]] = (i << 1) + 1;
}

int main()
{
	prm[++prm[0]] = 2;
	ciur3();
	fi >> m;
	while (m--)
	{
		fi >> a >> b;
		rez = 0;
		for (int i = 1; prm[i]*prm[i] <= b; ++i)
			if (b%prm[i] == 0)
			{
				dv[++dv[0]] = prm[i];
				while (b%prm[i] == 0)
					b /= prm[i];
			}
		if (b > 1)
			dv[++dv[0]] = b;
		mltm = (1 << dv[0]) - 1;
		for (int i = 1; i <= mltm; ++i)
		{
			aux = 1, smn = 0;
			for (int j = 0; (1 << j) <= mltm; ++j)
				if (i&(1 << j))
				{
					aux *= dv[j+1];
					++smn;
				}
			if (smn&1)
				rez += a/aux;
			else
				rez -= a/aux;
		}
		fo << a - rez << '\n';
		memset(dv, 0, sizeof(dv));
	}
}