#include <cstdio>
#include <cstring>
#include <cassert>

#define MAX 1000005

char nri[MAX];
int sol[MAX][8];

void ciur(){
	nri[1]=0,nri[0]=0;
	for(int i=2;i*i<=MAX;i++){
		if(nri[i]==0){
			for(int j=i;j<=MAX;j+=i){
				nri[j]++;
			}
		}
	}
}

FILE* fin=fopen("divprim.in","r");
FILE* fout=fopen("divprim.out","w");

int main(){
	
	ciur();

	for(int i=1;i<MAX;i++){
		memcpy(sol[i],sol[i-1],sizeof(sol[i]));
		sol[i][nri[i]]=i;
	}

	int t,n,k;
	fscanf(fin,"%d ",&t);
	for(int i=0;i<t;i++){
		fscanf(fin,"%d %d\n",&n,&k);
		assert(k!=0);
		fprintf(fout,"%d\n",sol[n][k]);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}