#include <fstream>
using namespace std;

int v[1000001], s[8][1000001], k[8];
int i, j, n, a, b;
int main()
{
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	for(i=2; i<=1000000; i++)
	{
		if(!v[i])
		{
			v[i]++;
			for(j=i+i; j<=1000000; j+=i)
			{
				v[j]++;
			}
		}
	}
	for(i=2; i<=1000000; i++)
	{
		k[v[i]]++;
		s[v[i]][k[v[i]]]=i;
	}
	f>>n;
	for(i=1; i<=n; i++)
	{
		f>>a>>b;
		g<<*(upper_bound(s[b]+1, s[b]+k[b]+1, a)-1)<<"\n";
	}
}