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

int nrd[1000001];
int a[8][1000001];
int t, n, k;

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

int main()
{
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	
	ciurc();
	
	for (int j = 1; j <= 1000000; ++j)
		a[0][j] = 1;
	for (int i = 1; i < 8; ++i)
		for (int j = 1; j <= 1000000; ++j)
		{
			a[i][j] = a[i][j - 1];
			if (nrd[j] == i)
				a[i][j] = j;
		}
	
	fin >> t;
	while (t--)
	{
		fin >> n >> k;
		fout << a[k][n] << '\n';
	}
}