#include <fstream>
using namespace std;
bool is_prime(long long x);
long long div_prim(long long x);
ifstream f("divprim.in");
ofstream g("divprim.out");
int main()
{
	long long T, n, k, i;
	f >> T;
	while (T--) {
		f >> n >> k;
		bool gasit = false;
		for(i=n;i>1 && gasit==false;i--)
			if (div_prim(i) == k) {
				g << i;
				gasit = true;
			}
		if (gasit == false) g << 0;
		g << endl;
	}
	f.close(); g.close();
}
bool is_prime(long long x){
	if (x == 2) return true;
	else if (!(x > 1 && (x % 2 || x == 2))) return false;
	else {
		bool OK = true; long long i;
		for (i = 3; i * i <= x && OK == true; i += 2)
			if (!(x % i)) OK = false;
		return OK;
	}
}

long long div_prim(long long x) {
	if (x == 1) return 0;
	else if (is_prime(x) == true) return 1;
	else {
		long long i, nr;
		for (nr = 0, i = 2; i <= x / 2; i++)
			if (!(x % i || is_prime(i) == false)) nr++;
		return nr;
	}
}