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