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

#define m 100000

std::vector<int> make()
{
	std::vector<int> myV;
	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;
			myV.push_back(i);
		}
	return myV;
}

int main()
{
	std::vector<int> myV = make();
	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;
		int k(0), j(0);
		bool *bC = new bool[a + 1];
		for(int j(0); j <= a; j++)
			bC[j] = true;
		while(myV[j] <= b)
		{
			if(b % myV[j] == 0)
			{
				for(int l(myV[j]); l <= a; l += myV[j])
					if(bC[l])
					{
						k++;
						bC[l] = false;
					}
			}
			j++;
		}
		out << a - k << "\n";
	}
	return 0;
}