#include <bits/stdc++.h>
#define cat_vrea second.first
#define cat_a_ramas second.second
#define nume_produs first
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
ifstream in ("divprim.in");
ofstream out ("divprim.out") ;

int viz [ 1000005 ] , n , t , last ;
int sol [ 8 ][ 10000005 ] ;
void ciur ()    {
    int i , k ;
    for ( i = 2 ; i <= 1000000 ; ++ i )   {
        if ( !viz [ i ] )   {
            for ( k = i ; k <= 1000000 ; k += i ) {
                viz [ k ] ++ ;
            }
        }
    }
}

int main () {
    int i, k;
    ciur() ;
    for ( k = 0 ; k < 8 ; ++ k )    {
        last = 0 ;
        for ( i = 1 ; i <= 1000000 ; ++ i )   {
            if ( viz [ i ] == k )   {
                last = i ;
            }
            sol [ k ][ i ] = last ;

        }
    }
    in >> t ;
    while ( t -- )  {
        in >> i >> k ;
        out << sol [ k ][ i ] << '\n';

    }
}