#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int NMAX = 1000000;
const int KMAX = 7;

int c[NMAX+2];
vector <int> v[8];
vector <int> :: iterator it;

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

void parc() {
    for( int i = 1;  i <= NMAX;  ++i )  if( c[i] <= 7 )  v[ c[i] ].push_back(i);
}

int main() {
    ciur();
    parc();
    int T,N,K;
    cin >> T;
    for( int i = 1;  i <= T;  ++i ) {
        cin >> N >> K;
        if( K == 0 && N >= 1 ) cout << 1;
        else if( v[K][0] > N ) cout << 0;
        else {
            it = upper_bound( v[K].begin(), v[K].end(), N );
            if( it != v[K].begin() ) --it;
            int x = *it;
            if( c[ x ] == K && x <= N ) cout << x;
            else cout << 0;
        }
        cout << '\n';
    }
    return 0;
}