#include <cstdio>

using namespace std;

const int NMAX = 100000;

int c[NMAX + 5], d[8][NMAX + 5];

void ciur() {
    for(int i = 2; i <= NMAX; ++ i) {
        if(c[i] == 0) {
            for(int j = i; j <= NMAX; j += i) {
                c[j] ++;
            }
        }
    }
}

void dnk() {
    for(int i = 1; i <= 7; ++ i) {
        for(int j = 2; j <= NMAX; ++ j) {
            if(c[j] == i)
                d[i][j] = j;
            else
                d[i][j] = d[i][j - 1];
        }
    }
}

int main() {
    freopen("divprim.in", "r", stdin);
	freopen("divprim.out", "w", stdout);

    ciur();
    dnk();

    int t, n, k;
    scanf("%d", &t);

    for(int i = 1; i <= t; ++ i) {
        scanf("%d%d", &n, &k);
        printf("%d\n", d[k][n]);
    }

    return 0;
}