#include <cstdio>

#define MAXN 1000010
#define MAXK 8

int main(){

  freopen("divprim.in", "r", stdin);
  freopen("divprim.out", "w", stdout);

  int T, N, K, i, j, maxn;
  static int Fact[MAXN], A[MAXN][MAXK];

  for(i=2; i<MAXN; i++)
    if(!Fact[i])
      for(j=i; j<MAXN; j+=i)
	Fact[j]++;
  
  for(i=0; i<MAXK; i++){
    maxn=0;
    for(j=1; j<MAXN; j++){
      if(Fact[j]==i)
	maxn=j;
      A[j][i]=maxn;
    }
  }

  scanf("%d", &T);

  while(T--){
    scanf("%d%d", &N, &K);
    printf("%d\n", A[N][K]);
  }

  return 0;

}