#include<cstdio>
using namespace std;
int ciur[1000001];
void ciurr(){
	int i, j;
	for(i=2;i<=1000000;i++)
		if(ciur[i]==0){
			for(j=2;j<=1000000/i;j++)
				ciur[i*j]++;
			ciur[i]=1;
		}
}
int a[8][1000001];
int main()
{
	int i,j,k,n,t;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	ciurr();
	for(i=1;i<=7;i++)
		for(j=1;j<=1000000;j++)
			if(ciur[j]==i)
				a[i][j]=j;
			else
				a[i][j]=a[i][j-1];
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d%d",&n,&k);
		printf("%d\n",a[k][n]);
	}

	return 0;
}