#include<fstream.h>
#define NMAX 1000001

int a[NMAX], n, k, t, sol[8][NMAX], x, y;

ifstream f("divprim.in");
ofstream g("divprim.out");

void ciur()
{
	int i, j;
	for (i=2; i<=NMAX-1; ++i)
	{
		if (a[i]==0) 
			{
				++a[i];
				for(j=i+i; j<=NMAX-1; j+=i) ++a[j];
			}
		for (j=1; j<8 ; ++j) sol[j][i]=sol[j][i-1];
		if (a[i]<8) sol[a[i]][i]=i;
	}
}

int main()
{
	ciur();
	f>>t;
	while (t--)
	{
		f>>x>>y;
		g<<sol[y][x]<<"\n";
	}
	f.close();
	g.close();
	return 0;
}