#include <bitset>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
const long long kMax = 1e6 + 5;
long long A, B;
bitset<kMax> isPrime;
vector<long long> primeList, divB;

void sieve()
{
	isPrime.set();
	isPrime[0] = isPrime[1] = false;

	primeList.push_back(2);
	for (long long i = 4; i < kMax; i += 2)
		isPrime[i] = false;

	for (long long i = 3; i < kMax; i += 2)
	{
		if (isPrime[i])
		{
			primeList.push_back(i);
			for (long long j = i * i; j < kMax; j += i)
				isPrime[j] = false;
		}
	}
}


int main()
{
	sieve();
	int t = 0;
	fin >> t;
	while (t--)
	{
		fin >> A >> B;

		int cb = B;
		for (size_t i = 0; i < primeList.size() && cb != 1; ++i)
		{
			if (!(cb % primeList[i]))
			{
				divB.push_back(primeList[i]);
				while (!(cb % primeList[i]))
					cb /= primeList[i];
			}
		}
		if (cb != 1)
			divB.push_back(cb);

		long long notInSet = 0;
		int sz = divB.size(), pwr = (1 << sz);
		for (int bitMask = 1; bitMask < pwr; ++bitMask)
		{
			int bitsSet = 0;
			long long factor = 1;
			for (int i = 0; i < sz; ++i)
			{
				if (bitMask & (1 << i))
				{
					++bitsSet;
					factor *= divB[i];
				}
			}

			if (bitsSet % 2)
				notInSet += (A / factor);
			else
				notInSet -= (A / factor);
		}

		fout << A - notInSet << '\n';

		divB.clear();
	}
	return 0;
}