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