#include <stdio.h>
#define MAX 1000001
FILE *fin, *fout;
int k, nr[ MAX ];
int n, t, a[ MAX ][ 7 ];

void matrice(){
    int i, j;
    for( i = 2; i * 2 < MAX; ++i )
        nr[ 2 * i ] = 1;
    nr[ 2 ] = 1;
    for( i = 3; i < MAX; i += 2 )
        if( nr[ i ] == 0 ){
            nr[ i ] = 1;
            for( j = 2; j * i < MAX; ++j )
                ++nr[ j * i ];
         }
    for( i = 2; i < MAX; ++i ){
        for( j = 0; j < 7; j++ )
            a[ i ][ j ] = a[ i - 1 ][ j ];
        if( nr[ i ] < 8 )
            a[ i ][ nr[ i ] - 1 ] = i;
    }
}

int main()
{
    matrice();
    fin = fopen( "divprim.in", "r" );
    fout = fopen( "divprim.out", "w" );
    fscanf( fin, "%d\n", &t );
    while( t-- ){
        fscanf( fin, "%d %d\n", &n, &k );
        if( k == 0 )
            fprintf( fout, "1\n" );
        else fprintf( fout, "%d\n", a[ n ][ k - 1 ] );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}