#include <fstream>
#include<vector>
#include<algorithm>
using namespace std;

ifstream in("divprim.in");
ofstream out("divprim.out");

int v[1000010], N, T, K;
vector<int>Map[10];

void ciur()
{
	for (int i = 2; i <= 1000000; i++)
	{
		if (v[i] == 0)
		{
			for (int j = i; j <= 1000000; j += i)
			{
				v[j] ++;
			}
		}
		Map[v[i]].push_back(i);
	}
}



int main()
{
	in >> T;

	ciur();

	while (T--)
	{
		in >> N >> K;

		int solution = upper_bound(Map[K].begin(), Map[K].end(), N) - Map[K].begin() - 1;
		if (solution  < 0)
		{
			out << 0 << '\n';
		}
		else
		{
			out << Map[K][solution] << '\n';
		}


	}
	return 0;
}