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

vector<bool> ciur(1000000);
int t, n, k;

void ciurc()
{
	for (int i = 3; i * i <= 1000000; i += 2)
		if (!ciur[i])
			for (int j = i * i; j <= 1000000; j += i << 1)
				ciur[j] = true;
}

int main()
{
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	ciurc();
	
	fin >> t;
	while (t--)
	{
		fin >> n >> k;
		if (k == 0)
			fout << 1 << '\n';
		else if (k == 1)
			fout << 2 << '\n';
		else
		{
			int nr = 1, now = 2;
			
			for (int i = 3; nr < k && now <= n; i += 2)
				if (!ciur[i])
				{
					++nr;
					now *= i;
				}
			
			if (nr < k || now > n)
				fout << 0 << '\n';
			else
				fout << now << '\n';
		}
	}
}