#include<stdio.h>
#include<math.h>
FILE *fin,*fout;
int t,n,k,v[1000001],i,j,r,q, a[1000001][8],s=1000001;
void nr_div(){
	int i,j;
	for(i=2;i<=s;i++){
		if(v[i]==0){
		for(j=i;j<=s;j+=i){
			v[j]++;
		}
		}
	}
	for(i=1;i<=s;i++){
		a[i][v[i]]=i;
		for(j=0;j<=8;j++){
			if(a[i-1][j]!=0 && a[i][j]==0){a[i][j]=a[i-1][j];}
		}
	}
}
int main(){
fin=fopen("divprim.in","r");
fout=fopen("divprim.out","w");
fscanf(fin,"%d",&t);
nr_div();
for(q=1;q<=t;q++){
	fscanf(fin,"%d %d",&n,&k);
	fprintf(fout,"%d\n",a[n][k]);
}
return 0;}