#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
const int maxn = 1000000;

int cnt[maxn + 1];

int main() {

    for (int i = 2; i <= maxn; i++) {
        if (cnt[i] == 0) {
            for (int j = i; j <= maxn; j += i) {
                cnt[j]++;
            }
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        int sol = 0;
        for (int x = n; x >= 1; x--) {
            if (cnt[x] == k) {
                sol = x;
                break;
            }
        }

        cout << sol << '\n';
    }

    return 0;
}