#include <iostream>
#include <fstream>
using namespace std;

#define MAX 1000100
typedef long long lol;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
int Q;
lol a, b;
bool p[MAX + 10];
int prime[MAX + 10];
int divlist[10];

inline lol sq(lol a)
{
	return a * a;
}

inline lol sqrt(lol number)
{
	lol i = 0, cnt = 1LL << 32;
	for (; cnt > 0; cnt >>= 1)
		if (sq(i + cnt) <= number)
			i += cnt;
	return i;
}

inline void makeDivisorsList(lol number)
{
	lol rad = sqrt(number);
	divlist[0] = 0;
	for (int i = 1; i <= prime[0] && number > 1 && prime[i] <= rad; i++)
	{
		if (number % prime[i] == 0)
			divlist[++divlist[0]] = prime[i];
		while (number % prime[i] == 0)
			number /= prime[i];
	}
	if (number > 1) divlist[++divlist[0]] = number;
}

inline lol pinex(lol a, lol b)
{
	lol res = 0;
	makeDivisorsList(b);
	for (int i = 1; i < (1 << divlist[0]); i++)
	{
		int prod = 1, sign = -1;
		for (int j = 0; j < divlist[0]; j++)
			if (i & (1 << j))
				prod = prod * divlist[j + 1], sign = -sign;
		res = res + (a / prod) * sign;
	}
	return a - res;
}

int main()
{
	for (int i = 2; i <= MAX; i++)
		if (p[i] == false)
		{
			prime[++prime[0]] = i;
			for (int j = min(1LL * MAX + 1, 1LL * i * i); j <= MAX; j += i)
				p[j] = true;
		}
	
	for (fin >> Q; Q > 0; Q--)
	{
		fin >> a >> b;
		fout << pinex(a, b) << '\n';
	}
	
	return 0;
}