#include <fstream>
#include <vector>
#include <bitset>

void erato(std::vector<int>& myV)
{
	int a = 1000005;
	std::bitset<1000005> myBit;
	for(unsigned i = 2; i < a; i++)
		if(myBit[i] == 0) 
		{
			myV.push_back(i);
			for(unsigned j = i * i; j < a; j += i)
				myBit[j] = 1;
		}
}

void exec(long long& sum, std::vector<int>& myV, std::vector<long long>& myP, int sgn, long long a)
{
	long long b = 1LL;
	for(unsigned i = 0; i < myV.size(); i++)
		b *= myP[myV[i]];
	b = a / b;
	b *= sgn;
	sum += b;
}

void bt(long long& sum, std::vector<int>& myV, std::vector<long long>& myP, int k, long long a, int sgn)
{
	if(myV.size() == k)
	{
		exec(sum, myV, myP, sgn, a);
		return;
	}
	int i;
	if(myV.empty()) i = 0;
	else i = myV.back() + 1;
	while(i < myP.size())
	{
		myV.push_back(i);
		bt(sum, myV, myP, k, a, sgn);
		myV.pop_back();
		i++;
	}
}

long long inclusion(std::vector<long long>& myP, long long a)
{
	long long sum = 0;
	for(unsigned i = 1; i <= myP.size(); i++)
	{
		std::vector<int> myV;
		int sgn;
		if((i + 1) % 2 == 0) sgn = 1;
		else sgn = -1;
		bt(sum, myV, myP, i, a, sgn);
	}
	return sum;
}


int main()
{
	std::vector<int> myV;
	erato(myV);
	int nV;
	long long a, b;
	std::ifstream in("pinex.in");
	std::ofstream out("pinex.out");
	in >> nV;
	for(int i = 0; i < nV; i++)
	{
		in >> a >> b;
		std::vector<long long> myP;
		for(unsigned i = 0; i < myV.size(); i++)
			if(b % myV[i] == 0) myP.push_back(myV[i]);
		if(myP.empty()) myP.push_back(b);
		out << a - inclusion(myP, a) << '\n';
	}
	return 0;
}