#include<fstream>

using namespace std;

ifstream f ("divprim.in");
ofstream g ("divprim.out");

int n, i, k, x, ok, ap[ 100001 ], j;

int main(){

    for( i = 2; i <= 100001; ++i ){
        if( ap[ i ] == 0 ){
            for( j = i; j <= 100001; j = j + i )
            ap[ j ]++;
        }
    }
    f >> n;
    for( i = 1; i <= n; ++i ){
        f >> x >> k;
        ok = 0;
        for( j = x; j >= 1 && ok == 0; --j )
            if( ap[ j ] == k ){
                g << j << '\n';
                ok = 1;
            }
        if( ok == 0 )g << 0 << '\n';
    }

    return 0;
}