#include <stdio.h>

#define END 1000000

int ciur[END],m[8][END];

int main() {
  int j, i;
  FILE *fin, *fout;
  fin = fopen( "divprim.in", "r" );
  fout = fopen( "divprim.out", "w" );
  for( i = 2; i <= END; i++) {
    if( ciur[i] == 0 ) {
      for(j = i; j <= END; j+=i )
        ciur[j]++;
    }
    for( j = 1; j <= 7; j++ )
      m[j][i] = m[j][i - 1];
    if( ciur[i] <= 7 )
      m[ciur[i]][i] = i;
  }
  int n,a,k;
  fscanf( fin, "%d", &n );
  for(int i=1; i<=n; i++) {
    fscanf( fin, "%d", &a );
    fscanf( fin, "%d", &k );
    fprintf( fout, "%d \n", m[k][a] );
  }
  return 0;
}