#include <bits/stdc++.h>

using namespace std;

ifstream fin("txt.in");
ofstream fout("txt.out");
const int Max = 1000000;
int t, n, k, i, j, nrf[Max + 2];
vector<int> r[12];

static inline void Ciur() {
    r[0].push_back(1);
    for(int i = 2; i <= Max; i++) {
        if(!nrf[i]) {
            for(int j = i; j <= Max; j += i) nrf[j]++;
        }

        r[nrf[i]].push_back(i);
    }
}

int main() {
    Ciur();
    fin >> t;
    while(t--) {
        fin >> n >> k;

        if(r[k].front() > n) fout << "0\n";
        else {
            int poz = 0;
            int put = (1 << 18);
            while(put) {
                if(put + poz < (int)r[k].size() && r[k][put + poz] <= n) poz += put;
                put >>= 1;
            }

            fout << r[k][poz] << "\n";
        }
    }

    return 0;
}