#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

/*

*/
const int maxk = 8;
const int maxn = 1000005;

int nr_div[maxn], t, n, k;
int ans[maxn][maxk];/// ans[i][j] = cel mai mare numar, mai mic sau egal cu i, care
            /// are j divizori

/// int fact[maxn]; fact[i] = fact[i - 1]* i;

void preprocess() {
    for(int i = 2 ; i < maxn ; ++ i) {
        if(nr_div[i] == 0) {
            nr_div[i] = 1;
           // cerr << i << ' ' ;
            for(int j = i + i ; j < maxn ; j += i)
                ++ nr_div[j];
            /// ans[i - 1][j] precalcula
          //  for(int j = 0 ; j < maxk ; ++ j)
           //     cerr << i << ' ' << j << ' ' << ans[i][j] << '\n';
        }
        for(int j = 0 ; j < maxk ; ++ j)
            ans[i][j] = ans[i - 1][j];  // luam intervalul [1, i - 1];
        if(nr_div[i] < maxk)
            ans[i][nr_div[i]] = i;
    }
}

int main() {
    preprocess();
    fin >> t;
    while(t -- ) {
        int N, K;
        fin >> N >> K;
        fout << ans[N][K] << '\n';
    }
    return 0;
}