#include <iostream>
#include <cstdio>

#define n_max 1000000
#define k_max 14

using namespace std;

int c[1000005],m[1000005][15];

void ciur()
{
    for ( int i = 2 ; i <= n_max ; i ++ )
        if ( not c[i] )
        {
            c[i] = 1 ;
            for ( int j = i + i ; j <= n_max ; j += i )
                c[j] ++ ;
        }
}

void sol()
{
    for ( int i = 1 ; i <= n_max ; i ++ )
    {
        for ( int j = 0 ; j <= k_max ; j ++ )
            m[i][j] = m[i-1][j] ;
        m[i][c[i]] = i ;
    }
}

void afish()
{
    int n ;
    scanf( "%d" , &n ) ;
    for ( ; n ; n -- )
    {
        int nr , k ;
        scanf( "%d %d" , &nr , &k ) ;
        printf( "%d\n" , m[nr][k] ) ;
    }
}

int main()
{
    freopen( "divprim.in" , "r" , stdin ) ;
    freopen( "divprim.out" , "w" , stdout ) ;
    ciur() ;
    sol() ;
    afish() ;
    return 0;
}