#include <stdio.h>
#define NMax 1000010
#define KMax 8
const char IN[]="divprim.in",OUT[]="divprim.out";

int Tes,N,K;
int T[NMax];
int Rez[NMax][KMax];

void ciur(){
	int i,j;
	for (i=2;i<=NMax;++i) if (!T[i]){
		for (j=i;j<=NMax;j+=i)
			++T[j];
	}
}

int main()
{
	int i,j;
	ciur();
	for (i=1;i<=NMax;Rez[i][T[i]]=i,++i)
		for (j=0;j<KMax;++j)
			Rez[i][j]=Rez[i-1][j];

	freopen(IN,"r",stdin);
	scanf("%d",&Tes);
	freopen(OUT,"w",stdout);
	while (Tes--)
		scanf("%d%d",&N,&K),
		printf("%d\n",Rez[N][K]);
	fclose(stdout);
	fclose(stdin);
	return 0;
}