# include <stdio.h>

const long int MAXN=1000000;
long int ciur[MAXN+1];
long int last[MAXN][8];
long int t;

void iniciur()
{
long int i,j;
for (i=2;i<=MAXN;i++)
	if (!ciur[i])
		{
		j=i;
		while (j<=MAXN)
			{
			ciur[j]++;
			j+=i;
			}
		}
}

void recreate()
{
long int i,j;
for (i=2;i<=MAXN;i++)
	for (j=0;j<=7;j++)
		if (ciur[i]==j) last[i][j]=i;
		else last[i][j]=last[i-1][j];
}

void solve()
{
long int a,b,i;
FILE *f=fopen("divprim.in","r"),*g=fopen("divprim.out","w");
fscanf(f,"%ld",&t);
for (i=1;i<=t;i++)
	{
	fscanf(f,"%ld%ld",&a,&b);
	fprintf(g,"%ld\n",last[a][b]);
	}
fcloseall();
}

int main()
{
iniciur();
recreate();
solve();
return 0;
}