#include<fstream>
#include <cstring>
using namespace std;
int p[1000000];
int main()
{
	bool ok;
	int h,i,j,K,n,T;
	memset(p, 0x0, sizeof(p));
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	n=1000000;
	for(i=2; i<=n; i++)
	{
		if(p[i]==0)
			for(j=i;j<=n;j+=i)
				p[j]++;
	}
	f>>T;
	for(h=1; h<=T; h++)
	{
		f>>n;
		f>>K;
		ok=false;
		for(i=n; i>=2; i--)
			if(p[i]==K)
			{
				ok=true;
				break;
			}
			if(ok)
				g<<i<<"\n";
			else
				g<<0<<"\n";
	}
	return 0;
}