#include<stdio.h>
int nr[1000005],div[1000005][8];
int main(){
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int n,k,t,i;
	
	for(i=2;i<1000002;i++){
		if(nr[i]==0){
			for(k=i;k<1000002;k+=i)
				nr[k]++;
		}
	}
	
	for(i=2;i<1000002;i++){
		for(k=0;k<7;k++){
			div[i][k]=div[i-1][k];
		}
		div[i][nr[i]]=i;
	}
	
	scanf("%d",&t);
	for(i=0;i<t;i++){
		scanf("%d %d",&n,&k);
		printf("%d\n",div[n][k]);
	}
	
	
	return 0;
}