#include <stdio.h>
using namespace std;
#define nmax 1000005
#define K 8

int count[nmax], max[K][nmax];
int main ()
{
	int i,j,n,k,t;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	for (i = 2; i < nmax;i += 2)
	{
		count[i]=1;
	}
	for (i = 3;i < nmax; i += 2)
	{
		if(count[i]==0)
			for (j = i; j < nmax; j+=i)
				count[j]++;
	}
	for (i = 1;i < nmax; ++i)
	{
		for (j=0;j<K;j++)
		{
			if(count[i]==j)
				max[j][i]=i;
		    else
			{
			   max[j][i]=max[j][i-1];
			}
	    }
	}
	scanf("%d", &t);
	for (i = 1; i <= t; ++i)
	{
		scanf("%d %d ",&n,&k);
		printf("%d\n",max[k][n]);
	} 
 return 0;
}