#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int NMAX = 1000005;

long long t, a, b;
bool c[NMAX];
vector<long long>primes;
vector<long long>sol;

void ciur(int n)
{
	c[0] = c[1] = 1;
	for (int i = 4; i <= n; i += 2)
		c[i] = 1;
	int lim = (int)sqrt((double)n);
	for (int i = 3; i <= lim; i += 2)
	{
		if (!c[i])
		{
			for (int j = i * i; j <= n; j += 2 * i)
				c[j] = 1;
		}
	}
}

long long solve(long long a, long long b)
{
	sol.clear();
	long long e;
	int k = 0;
	int lim = (int)sqrt((double)b);
	while (primes[k] <= 1ll * lim && b > 1 && k < primes.size())
	{
		e = 0;
		while (b % primes[k] == 0)
		{
			b /= primes[k];
			e++;
		}
		if (e > 0)
			sol.push_back(primes[k]);
		k++;
	}
	if (b > 1)
		sol.push_back(b);
	long long sum = 0;
	int ns = (1 << sol.size());
	for (int f = 0; f < ns; f++)
	{
		int cnt = 0;
		long long prod = 1;
		for (int i = 0; i < sol.size(); i++)
		{
			if (f & (1 << i))
			{
				cnt++;
				prod *= sol[i];
			}
		}
		if (cnt == 0) continue;
		if (cnt & 1)
			sum += (a / prod);
		else
			sum -= (a / prod);
	}
	return sum;
}

int main()
{
	ciur(1000000);
	for (int i = 1; i <= 1000000; i++)
		if (!c[i]) primes.push_back(i);
	fin >> t;
	while (t--)
	{
		fin >> a >> b;
		fout << a-solve(a, b) << '\n';
	}
	return 0;
}