#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<long long> divs;

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

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

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();
		int j = 0;
		for(unsigned int i=0;i<primes.size() && b!=1; ++ i)
			if (b % primes[i] == 0)
			{
				divs.push_back(primes[i]);

				while (b % primes[i] == 0)
					b /= primes[i];
			}
		if(b != 1)
			divs.push_back(b);
		
		cout << a - wrong(0, 1l) << endl;
	}

	return 0;
}