# include <cstdio>

const char FIN[] = "divprim.in", FOU[] = "divprim.out" ;
const int MAX = 1000000 ;

int mat[ 8 ][ 380000 ];
int lung[ 8 ] ;
int N, K, T ;
short phi[ MAX + 5 ] ;

void ciur ( void ) {
    for ( int i = 2; i <= MAX; i += 2 ) {
        phi[ i ] = 1 ;
    }

    for ( int i = 3; i <= MAX; i += 2 ) {
        if ( phi[ i ] == 0 ) {
            for ( int j = i << 1; j <= MAX; j += i ) {
                ++phi[ j ] ;
            }
            phi[ i ] = 1 ;
        }
    }

    for ( int i = 2; i <= MAX; ++i ) {
        mat [ phi[ i ] ][ ++lung [ phi[ i ] ] ] = i ;
    }
}

int cb () {
    int i, cnt;

    for (cnt = 1; cnt <= lung[ K ]; cnt <<= 1) ;
    for (i = 0; cnt; cnt >>= 1) {
        if (i + cnt <= lung[ K ] && mat[ K ][i + cnt] <= N) {
            i += cnt;
        }
    }

    return i;
}

int solve ( void ) {
    if ( mat[K][0] > N ) {
        return 0 ;
    } else {
        int aux = cb () ;
        if ( mat[K][aux] <= N ) {
            return mat[K][aux] ;
        } else {
            return 0;
        }
    }
}

int main() {
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    ciur () ;

    for ( scanf ( "%d", &T ) ; T ; --T ) {
        scanf ( "%d %d", &N, &K ) ;
        printf ( "%d\n", solve () ) ;
    }

    return 0 ;
}