#include <fstream>
using namespace std;

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

const int N = 1000000;
int v[N + 2], a[N + 2][10], n, k, t;

void ciur () {
	for (int i = 2; i <= N; ++i) {
		if (v[i]) {
			continue;
		}
		for (int j = i; j <= N; j += i) {
			++v[j];
		}
	}
}

void exe () {
	ciur ();
	for (int i = 1; i <= N; ++i) {
		a[i][v[i]] = i;
		for (int j = 0; j <= 7; ++j) {
			a[i][j] = max(a[i - 1][j], a[i][j]);
		}
	}
}

void citire () {
	in >> t;
}

void afisare () {
	for (; t; --t) {
		in >> n >> k;
		out << a[n][k] << '\n';
	}
}

int main () {
	citire ();
	
	exe ();
	
	afisare ();
	
	return 0;
}