#include <stdio.h>
#define N_MAX 1000000
int nrd[ N_MAX + 1 ][ 8 ], indici[ 8 ];
int v[ N_MAX + 1 ];

void ciur ( int n ){
    int i, j;
    for ( i = 2; i * i <= n; i++ ){
        if ( v[ i ] == 0 ){
            for ( j = i; j <= n; j += i ){
                v[ j ]++;
            }
        }
    }
    for ( j = 0; j <= n; j++ ){
        nrd[ indici[ v[ j ] ] ][ v[ j ] ] = j;
        indici[ v[ j ] ]++;
    }
    return ;
}
int caut ( int n, int k ){
    int pas = 1 << 30, i = 0, gasit = 0;
    while ( pas > 0 ){
        if ( i + pas < indici[ k ] ){
            if ( nrd[ i + pas ][ k ] <= n ){
                   i += pas;
                   gasit = 1;
            }
        }
        pas /= 2;
    }
    if ( nrd[ 0 ][ k ] <= n ){
        gasit = 1;
    }
    if ( !gasit )   return 0;
    return nrd[ i ][ k ];
}

int main()
{
    FILE *in = fopen ( "divprim.in", "r" );
    int t;
    fscanf ( in, "%d", &t );
    ciur ( N_MAX );
    int i, n, k;
    FILE *out = fopen ( "divprim.out", "w" );
    for ( i = 0; i < t; i++ ){
        fscanf ( in, "%d%d", &n, &k );
        fprintf ( out, "%d\n", caut ( n, k ) );
    }
    fclose ( in );
    fclose ( out );
    return 0;
}