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

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

int cautareBinara() {
    int st = 0, dr = v[k].size() - 1, rez = 0;
    if (dr > n)
        dr = n;
    if (v[k][0] > n)
        return 0;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (v[k][mij] <= n) {
            rez = v[k][mij];
            st += mij + 1;
        }
        else
            dr = mij - 1;
    }
    return rez;
}

int main() {
    ciur();
    fin >> t;
    while (t--) {
        fin >> n >> k;
        fout << cautareBinara() << "\n";
    }
    return 0;
}