#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define VMAX 1000000
#define NMAXDP 7

int nrdp[VMAX+1], v[VMAX], cnt_nrdp[NMAXDP+1], poz_dp[NMAXDP+1];

int main() {
    FILE *in, *out;
    int d, m, i, t, n, k, ndp_i, st, dr, mij, rez;
    // ciurul
    for (d = 2; d <= VMAX; d++) {
        if (nrdp[d] == 0) {
            for (m = d; m <= VMAX; m += d) {
                nrdp[m]++;
            }
        }
    }
    for (i = 1; i <= VMAX; i++) {
        cnt_nrdp[nrdp[i]]++;
    }
    for (i = 1; i <= NMAXDP; i++) {
        poz_dp[i] = poz_dp[i-1] + cnt_nrdp[i-1];
    }
    for (i = 1; i <= VMAX; i++) {
        ndp_i = nrdp[i];
        v[poz_dp[ndp_i]++] = i;
    }
    poz_dp[0] = 0;
    for (i = 1; i <= NMAXDP; i++) {
        poz_dp[i] = poz_dp[i-1] + cnt_nrdp[i-1];
    }
    in = fopen("divprim.in", "r");
    out = fopen("divprim.out", "w");
    fscanf(in, "%d", &t);
    for (i = 0; i < t; i++) {
        fscanf(in, "%d%d", &n, &k);
        // cautam binar cel mai mare numar cu k divizori <= n
        st = poz_dp[k];
        dr = poz_dp[k] + cnt_nrdp[k] - 1;
        rez = 0;
        while (st <= dr) {
            mij = (st + dr) / 2;
            if (v[mij] <= n) {
                rez = v[mij];
                st = mij + 1;
            } else {
                dr = mij - 1;
            }
        }
        fprintf(out, "%d\n", rez);
    }
    fclose(in);
    fclose(out);
    return 0;
}