#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int KMAX = 7, NMAX = 1000001;

struct heap_element {
	int idx, val;
} heel[KMAX];

int a[KMAX * 3][NMAX] = {};

inline bool he_comp(short a, short b)
{
	return heel[a].val > heel[b].val;
}

void gen_numbers(int X[KMAX][NMAX])
{
	int i, x, nr[NMAX] = {1}, K = 0, divp[NMAX] = {0, 1};
	heap_element *q;
	short primes[KMAX + 1] = {2, 3, 5, 7, 11, 13, 17}, heind[KMAX + 1] = {};
	for (i = 0; i != KMAX; ++i) {
		heel[i].val = primes[i];
		heel[i].idx = 0;
		heind[i] = i;
	}
	make_heap(heind, heind + KMAX, he_comp);
	do {
		x = heind[0];
		pop_heap(heind, heind + KMAX, he_comp);
		q = &heel[x];
		if ( q -> val != nr[K] ) {
			nr[++K] = q -> val;
			divp[K] = divp[q -> idx] + (bool)(nr[q -> idx] % primes[x]);
		}
        q -> val = primes[x] * nr[++(q -> idx)];
		push_heap(heind, heind + KMAX, he_comp);

			 
	} while (nr[K] <= NMAX);
	
	for (i = 1; i != K; ++i) {
        x = ++X[divp[i] - 1][0];
		X[divp[i] - 1][x] = nr[i];
    }
	
}
// So, shall we implement a BS or interpolation?
int search(int k, int q)
{
    int *x = a[k];
    int L = x[0], step, i;
    // let's go with BS
    for (step = 1; step <= L; step <<= 1);
    for (i = 0; step; step >>= 1) {
        if (i | step <= L)
            if (x[i | step] <= q) i |= step;
    }
    if (i) return x[i];
    else return 0;
}

int main()
{
    int T, t, N, K;
	gen_numbers(a);
    ifstream fin("divprim.in");
    freopen("divprim.out", "w", stdout);
    fin >> T;
    for (t = 0; t != T; ++t) {
        fin >> N >> K;
        if (K == 0) printf("0\n");
        else printf("%d\n", search(K - 1, N));
    }
    
	
	return 0;
}