#include <fstream>
#include <vector>
#include <cmath>

#define m 100000

int main()
{
	bool c[m];
	for(int i(0); i < m; i++)
		c[i] = true;
	for(int i(2); i <= sqrt(m); i++)
		if(c[i])
			for(int j(i * i); j < m; j += i)
				c[j] = false;
	std::ofstream out("pinex.out");
	std::ifstream in("pinex.in");
	int nC, a, b;
	in >> nC;
	for(int i(0); i < nC; i++)
	{
		in >> a >> b;
		bool *bC = new bool[a + 1];
		for(int j(0); j <= a; j++)
			bC[j] = true;
		int k(0);
		std::vector<int> myV;
		for(int j(2); j <= b; j++)
			if(c[j] && b % j == 0) myV.push_back(j);
		for(unsigned j(0); j < myV.size(); j++)
			for(int l(myV[j]); l <= a; l += myV[j])
				if(bC[l])
				{
					k++;
					bC[l] = false;
				}
		out << a - k << "\n";
	}
	return 0;
}