#include <fstream>
#define MAX 1000010

using namespace std;

int vec[MAX];
bool v[MAX];
int ciur[79000];

void CreateCiur()
{
	v[0] = v[1] = true;
	for (int i = 3;i*i <= MAX - 2;i += 2)
	{
		v[i + 1] = true;
		if (v[i] == false)
		{
			for (int j = i*i;j < MAX;j += i)
				v[j] = true;
		}
	}
	int k = 0;
	for (int i = 1;i < MAX;i++)
		if (v[i] == false)
			ciur[++k] = i;
	ciur[0] = k;
	/*for (int i = 1;i <= 100;i++)
		cout << ciur[i] << " ";*/
}

void CreateA()
{
	for (int i = 1;i <= ciur[0];i++)
		for (int j = ciur[i];j < MAX;j += ciur[i])
			vec[j]++;
	/*for (int i = 1;i < 100;i++)
		cout << vec[i] << " ";*/
}

void ReadAndSolve()
{
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int t;
	f >> t;
	for (int i = 1;i <= t;i++)
	{
		int n, k;
		f >> n >> k;
		while (vec[n] != k && n)
			n--;
		if (n == 0)
			g << 0 << "\n";
		else
			g << n << "\n";
	}
	f.close();
	g.close();
}

int main()
{
	CreateCiur();
	CreateA();
	ReadAndSolve();
	return 0;
}