#include <fstream>
#include <bitset>

using namespace std;

const int SIEVE_LIMIT = 1000000;
const int PRIMES_CNT = 78498;
const int MAX_FACT = 30;

bitset <SIEVE_LIMIT + 1> notPrime;
int primes[PRIMES_CNT], np;

void sieve()
{
	int i;
	for (i = 3; i * i <= SIEVE_LIMIT; i += 2)
	{
		if (!notPrime[i])
		{
			primes[np++] = i;
			for (int j = i * i; j <= SIEVE_LIMIT; j += (i << 1))
				notPrime[j] = 1;
		}
	}
	for (; i <= SIEVE_LIMIT; i += 2)
		if (!notPrime[i])
			primes[np++] = i;
	primes[np++] = 1000000;
}

int breakFactors(long long x, long long fact[])
{
	int cnt = 0, i;
	long long q;

	if (!(x & 1))
	{
		fact[cnt++] = 2LL;
		x /= (x & -x);
	}
	i = 0;
	while (1LL * primes[i] * primes[i] <= x)
	{
		q = x / primes[i];
		if (x == q * primes[i])
		{
			fact[cnt++] = primes[i];
			do
			{
				x = q;
				q = x / primes[i];
			} while (x == q * primes[i]);
		}
		i++;
	}
	if (x > 1)
		fact[cnt++] = x;
	return cnt;
}

long long solve(const long long &A, const long long &B)
{
	long long fact[MAX_FACT], res = 0LL;
	int z = breakFactors(B, fact);

	for (int i = (1 << z) - 1; i; i--)
	{
		long long prod = 1LL;
		int num = 0;
		for (int j = 0; j < z; j++)
		{
			if ((i >> j) & 1)
			{
				num++;
				prod *= fact[j];
			}
		}
		if (num & 1)
			res += A / prod;
		else
			res -= A / prod;
	}
	return A - res;
}

int main()
{
	ifstream in("pinex.in");
	ofstream out("pinex.out");
	long long A, B;
	int T;

	in >> T;
	
	sieve();

	while (T--)
	{
		in >> A >> B;
		out << solve(A, B) << '\n';
	}
	in.close();
	out.close();
	return 0;
}