#include <cstdio>
#include <iostream>

using namespace std;

const int NMAX = 1000 * 1000;
const int KMAX = 7;
int c[NMAX + 1];
int sol[KMAX + 1][NMAX + 1];

void ciur(){
  for( int i = 2; i <= NMAX; ++i )
    if( c[i] == 0 )
      for( int j = i; j <= NMAX; j += i )
        ++c[j];
}

void precal( int k ){
  int maxx;
  maxx = 0;
  for( int i = 2; i <= NMAX; ++i ){
    if( c[i] == k )
      maxx = i;
    sol[k][i] = maxx;
  }
}

int main()
{
    freopen( "divprim.in", "r", stdin );
    freopen( "divprim.out", "w", stdout );
    ciur();
    for( int i = 1; i <= KMAX; ++i )
      precal(i);
    int t, a, b;
    scanf( "%d", &t );
    while( t-- ){
      scanf( "%d%d", &a, &b );
      printf( "%d\n", sol[b][a] );
    }
    return 0;
}