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

#define VMAX 1000000
#define NMAXDP 7
//290914
int v[(NMAXDP+1)*VMAX];
char nrdp[VMAX+1];

int main() {
    FILE *in, *out;
    int d, m, i, j, 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++) {
        for (j = 0; j <= NMAXDP; j++) {
            if (nrdp[i] == j) {
                v[j*VMAX+i] = i;
            } else {
                v[j*VMAX+i] = v[j*VMAX+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);
        fprintf(out, "%d\n", v[k*VMAX+n]);
    }
    fclose(in);
    fclose(out);
    return 0;
}