#include<fstream>
using namespace std;

const int N=1000001;

int main()
{
	ifstream in("divprim.in");
	ofstream out("divprim.out");
	int n,k,t,i,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;
}