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

void ciur() {
    for (long long i = 2; i * i <= LMAX; i += 2) {
        if (prim[i] == 0)
            for (long long j = i * 2; 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;
}