#include<stdio.h>
using namespace std;
#define MAXN 100000

int v[8][MAXN], l[8], div[MAXN];
int main(){
  FILE*fin=fopen("divprim.in", "r");
  FILE*fout=fopen("divprim.out", "w");
  int d, p, q, i, j, n, k, rez, pas;
  for ( d = 2; d * d <= MAXN; d++ )
    if(div[d]== 0){
      div[d]=1;
      l[1]++; v[1][l[1]]=d;
      for(i=d*2; i<=MAXN; i+=d)
        div[i]++;
    }
  for(i=1; i<=MAXN; i++){
    l[div[i]]++;
    v[div[i]][l[div[i]]]=i;
  }
  printf("%d", v[2][1]);
  fscanf(fin, "%d", &q);
  for(p=1; p<=q; p++){
    fscanf(fin, "%d%d", &n, &k);
    rez=0;
    for(pas=1<<18; pas; pas>>=1)
      if(rez+pas<=l[k] && v[k][rez+pas]<=n){
        rez+=pas;
      }
    fprintf(fout, "%d\n", v[k][rez]);
  }
  return 0;
}