// Mihai Priboi

#include <stdio.h>
#include <stdlib.h>
#define N 1000000

char ciur[N + 1];
int kdivprim[7][N + 1];

int main() {
  FILE *fin, *fout;
  int t, n, k, d, i, j;
  // ciur cu numarul de divizori primi
  for( d = 2; d <= N; d++ ) {
    if( ciur[d] == 0 ) {
      for( i = d; i <= N; i += d )
        ciur[i]++;
    }
  }
  // precalculam o matrice in care pentru numarul k de divizori pe pozitia i se afla cel mai mare <= cu i cu k divizori
  for( i = 2; i <= N; i++ ) {
    for( j = 0; j < 7; j++ )
      kdivprim[j][i] = kdivprim[j][i - 1];
    kdivprim[ciur[i] - 1][i] = i;
  }
  fin = fopen( "divprim.in", "r" );
  fout = fopen( "divprim.out", "w" );
  fscanf( fin, "%d", &t );
  for( i = 0; i < t; i++ ) {
    fscanf( fin, "%d%d", &n, &k );
    fprintf( fout, "%d\n", k > 0 ? kdivprim[k - 1][n] : 1 );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}