#include <cstdio>

using namespace std;

const int NMAX = 1e6;
const int NRDIVMAX = 7;
unsigned char divprim[NMAX + 1];
int divmax[NRDIVMAX + 1][NMAX + 1];

static inline int max(int a, int b){
  return a < b ? b : a;
}

int main() {
  FILE *fin, *fout;
  fin = fopen( "divprim.in", "r" );
  fout = fopen( "divprim.out", "w" );
  int t, i, j, x, nrdiv;

  for( i = 2; i <= NMAX; ++i )
    if( !divprim[i] )
      for( j = i; j <= NMAX; j += i )
        ++divprim[j];
  for( i = 1; i <= NMAX; ++i )
    divmax[0][i] = 1;
  for( i = 2; i <= NMAX; ++i )
    divmax[divprim[i]][i] = i;
  for( i = 1; i <= NRDIVMAX; ++i )
    for( j = 1; j <= NMAX; ++j )
      divmax[i][j] = max(divmax[i][j], divmax[i][j - 1]);

  fscanf( fin, "%d", &t );
  while( t-- ){
    fscanf( fin, "%d%d", &x, &nrdiv );
    fprintf( fout, "%d\n", divmax[nrdiv][x] );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}