#include <bits/stdc++.h>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");
const int Max = 1000000;
int t, n, k, i, j, divi[Max + 2];
vector<int> pr[8];

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

        pr[divi[i]].push_back(i);
    }
}

static inline void Calc() {
    fin >> n >> k;

    if(pr[k].front() > n) fout << "0\n";
    else {
        int st = 0, dr = pr[k].size() - 1;
        int poz = st;

        while(st <= dr) {
            int mij = st + (dr - st) / 2;

            if(pr[k][mij] <= n) {
                poz = mij;
                st = mij + 1;
            }
            else dr = mij - 1;
        }

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

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

    return 0;
}