#include <fstream>
#include <vector>
using namespace std;
unsigned long long nr_div_prim(unsigned long long n)
{
	unsigned long long d = 2, p, nr = 0;
	while (n > 1) {
		p = 0;
		while (!(n % d)) { n /= d; ++p; }
		if (p > 0) ++nr;
		++d;
		if (n > 1 && d * d > n) d = n;
	}
	return nr;
}
ifstream f("divprim.in");
ofstream g("divprim.out");
int main()
{
	unsigned long long T, n, k,i; bool gasit;
	f >> T;
	while (T--) {
		f >> n >> k;
		vector<unsigned long long>ciur(n + 1);
		gasit = false;
		for(i=ciur.size()-1;i>1 && gasit==false;--i)
			if (nr_div_prim(i) == k) {
				g << i << endl;
				gasit = true;
			}
		if (gasit == false) g << 0 << endl;
		ciur.clear();
	}
	f.close(); g.close();

}