#include<stdio.h>
#define max 1000000
int ciur[max], sol[max][7], i, j, n, k, t, nr;
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	for (i=2;i<=max;i++)
		if (ciur[i]==0){
			j=1;
			while (i*j<=max){
				ciur[i*j]++;
				j++;
			}
		}
	for (nr=1;nr<=t;nr++){
		scanf("%d%d",&n,&k);
		for (i=1;i<=n;i++){
			for (j=1;j<=k;j++)
				sol[i][j]=sol[i-1][j];
			sol[i][ciur[i]]=i;
		}
		printf("%d\n",sol[n][k]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}