#include <fstream>

using namespace std;
ifstream cin ( "divprim.in" );
ofstream cout ( "divprim.out" );
int v[8];
int ciurdivprim[1000001];
int divprim[8][1000001];
int main()
{
    int t, n, k, i, d, mij, st, dr, poz;
    cin >> t;
    for ( i = 2; i <= 1000000; i++ ) {
     if ( ciurdivprim[i] == 0 ) {
        ciurdivprim[i] = 1;
        for ( d = 2 * i; d <= 100000; d += i )
          ciurdivprim[d]++;
     }
    }
    for ( i = 1; i <= 1000000; i++ ) {
        divprim[ciurdivprim[i]][v[ciurdivprim[i]]] = i;
        v[ciurdivprim[i]]++;
    }
    for ( i = 1; i <= t; i++ ) {
      cin >> n >> k;
      st = 0;
      dr = v[k];
      poz = -1;
      while ( st <= dr ) {
        mij = ( st + dr ) / 2;
        if ( divprim[k][mij] <= n ) {
          st = mij + 1;
          poz = mij;
        }
        else
          dr = mij - 1;
      }
      if ( poz != -1 )
        cout << divprim[k][poz] << "\n";
      else
        cout << "0\n";
    }
    return 0;
}