#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
#endif

const int MAX = 1000000;
int t, n, k, i, j, dp[MAX + 2];
vector<int> v[9];

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    for(i = 2; i <= MAX; i += 2) dp[i]++;
    for(i = 3; i <= MAX; i += 2) {
        if(0 == dp[i]) {
            for(j = i; j <= MAX; j += i) {
                dp[j]++;
            }
        }
    }

    for(i = 0; i < 7; i++) v[i].push_back(0);
    for(i = 2; i <= MAX; i++) {
        if(dp[i] <= 7) {
            v[dp[i] - 1].push_back(i);
        }
    }

    fin >> t;
    while(t--) {
        fin >> n >> k;
        k--;
        auto it = prev(upper_bound(v[k].begin(), v[k].end(), n));
        fout << *(n == *it ? prev(it) : it) << '\n';
    }

    return 0;
}