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