#include <iostream>
#include <fstream>
#define LMAX 1000005
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");
int prim[LMAX];
int t, st, dr, k, loc;

void ciur() {
    for (int i = 2; i <= LMAX; i += 2) {
        if (prim[i] == 0)
            for (int j = i; j <= LMAX; j += i)
                ++prim[j];
        if (i == 2)
            --i;
    }
    return;
}

int main() {
    ciur();
    fin >> t;
    while (t--) {
        fin >> dr >> k;
        while (dr > 0) {
            if (prim[dr] == k)
                break;
            --dr;
        }
        fout << dr << "\n";
    }
    return 0;
}