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

vector<int> primes;

void initPrimes()
{
	primes.clear();
	vector<char> a;
	a.resize(1000001);
	for(int i=2;i<1000000;++i)
		if (a[i] == 0)
		{
			primes.push_back(i);
			for(int j=i+i;j<1000000;j+=i)
				a[i]=1;
		}
}

long long m, a, b;
vector<int> divs;

long long wrong(int i = 0, long long num = 1, char sig = 1)
{
	if(i >= divs.size())
		return 0;

	long long cnt = wrong(i + 1, num, sig);
	num *= divs[i];
	cnt += sig * (a / num);
	cnt += wrong(i + 1, num, sig * -1);
}

int main()
{
	initPrimes();

	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	divs.reserve(60);
	cin >> m;

	while (m --)
	{
		cin >> a >> b;
		
		divs.clear();
		for(int i=0;i<primes.size() && b; ++ i)
			while(b % primes[i] == 0)
				divs.push_back(primes[i]),
				b /= primes[i];
		
		cout << a - wrong() << endl;
	}

	return 0;
}