#include<fstream>
const int N=1000005;
using namespace std;
int main()
{
	ifstream in("divprim.in");
	ofstream out("divprim.out");
	int n, k, T,  i, nr=0, j;
	char c[N]={0};
	for(j=2; j<N; j+=2)
		++c[j];
	for(i=3; i<N; i+=2)
		if(c[i]==0)
			for(j=i; j<N; j+=i)
				++c[j];
	in>>T;
	while(T--)
	{
		in>>n>>k;
		while(n && c[n]!=k)
			--n;
		out<<n<<"\n";
	}
	in.close();
	out.close();
	return 0;
}