#include <fstream>

using namespace std;

int m[1000001][8];
int K, N;

int main()
{
	int T, i, j;
	int v[1000001];
	memset (v, 0, sizeof (v));
	memset (m, 0, sizeof (m));
	v[1] = 0;
	m[1][0] = 0;

	for (i = 2; i <= 1000000; i++)
	{
		if (!v[i])
		{
			for (j = i; j <= 1000000; j += i)
			{
				v[j]++;
			}
		}

		for (j = 0; j <= 7; j++)
		{
			m[i][j]=m[i-1][j];
		}

		if (v[i] <= 7)
		{
			  m[i][v[i]] = i;
		}
	}


	ifstream fin ("divprim.in");
	ofstream fout ("divprim.out");
	fin >> T;

	for (j = 0; j < T; j++)
	{
		fin >> N >> K;
		fout << m[N][K] << "\n";
	}

	fin.close ();
	fout.close ();
	return 0;
}