#include <iostream>
#include <fstream>

using namespace std;

const int maxn = 1000001;
int ciur[maxn];

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

int main() {
    eratostene();
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    int t;
    fin >> t;
    for (int i = 0; i < t; i++) {
        int n, k;
        fin >> n >> k;
        int ans = 0;
        for (int j = n; j > 1; j--)
            if (ciur[j] == k) {
                ans = j;
                j = 1;
            }
        fout << ans << '\n';
    }

    return 0;
}