#include <bits/stdc++.h>
using namespace std;
#define x1 "divprim.in"
#define x2 "divprim.out"
ifstream in(x1);
ofstream out(x2);
#define NMAX 1000000
#define DMAX 8
int d[NMAX],mat[NMAX][DMAX];
void ciur() {
    for(int i = 2; i < NMAX; i++)
        if(d[i] == 0)
            for(int j = i; j < NMAX; j += i)
                d[j]++;
}
int main() {
    int n, k, q;
    in >> q;
    ciur();
    for(int i = 1; i < NMAX; i++) {
        for(int j = 0; j < DMAX; j++)
            if(d[i] == j)
                mat[i][j] = i;
            else
                mat[i][j] = mat[i - 1][j];
    }
    while(q--) {
        in >> n >> k;
        out << mat[n][k] <<'\n';
    }
    return 0;
}