#include<stdio.h>
int d[1000001],m[1000001][8];
void ciur_div(){
	int i,j;
	for(i=2;i<=1000000;i+=2){
		++d[i];
	}
	for(i=3;i<=1000000;i++){
		if(d[i]==0){
			for(j=i;j<=1000000;j+=i){
				++d[j];
			}
		}
	}
}
void make_m(){
	int i,j;
	for(i=2;i<=1000001;i++){
		for(j=0;j<8;j++){
			m[i][j]=m[i-1][j];
		}
		m[i][d[i]]=i;
	}
}
int main(){
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,k,n,i;
	ciur_div();
	make_m();
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d%d",&n,&k);
		printf("%d\n",m[n][k]);
	}
	return 0;
}