#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);
		for(int j(2); j <= b; j++)
			if(c[j] && b % j == 0)
				for(int l(j); l <= a; l += j)
					if(bC[l])
					{
						bC[l] = false;
						k++;
					}
		out << a - k << "\n";
	}
	return 0;
}