/*#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
bool prim(int x)
{
	for (int i = 2; i <= sqrt(x); i++)
	{
		if (x % i == 0)
		{
			return false;
		}
	}
	return true;
}
int omega(int x)
{
	if (x == 1)
		return 0;
	else
	{
		int s = 0;
		for (int i = 2; i <= x; i++)
		{
			if (prim(i))
			{
				if (x % i == 0)
					s++;
			}
		}
		return s;
	}
}
int main()
{
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	int T, N, K;
	fin >> T;
	for (int i = 1; i <= T; i++)
	{
		fin >> N >> K;
		for (int j = N; j >=1; j--)
		{
			if (omega(j) == K)
			{
				fout << j << endl;
				break;
			}
			if (j == 1)
				fout << 0 << endl;
		}
	}
}*/
#include <iostream>
#include <fstream>
using namespace std;
int prim[1000001], v[1000001][7];
int main()
{
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	int T, N, K;
	for (int i = 2; i <= 1000000; i++)
	{
		if (prim[i] == 0)
		{
			for (int j = i; j <= 1000000; j += i)
				prim[j]++;
		}
	}
	for (int i = 2; i <= 1000000; i++)
	{
		for (int j = 1; j <= 7; j++)
		{
			v[i][j] = v[i - 1][j];
		}
		v[i][prim[i]] = i;
	}
	fin >> T;
	for (int i = 1; i <= T; i++)
	{
		fin >> N >> K;
		fout << v[N][K] << '\n';
	}
}