#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int T,
	N, K;

bool prim[1000001];
int divizori[1000001];
int sol[1000001][8];

void ciur() {
	memset(prim, 1, sizeof(prim));
	for (int i = 2; i < 500001; ++i)
		if (prim[i]) {
			++divizori[i];
			for (int j = i+i; j < 1000001; j += i) 
				prim[j] = false,
				++divizori[j];
		}
}

int main(int argc, char *argv[]) {
	ciur();
	for (int i(2); i <= 1000000; ++i) {
		memcpy(sol[i], sol[i-1], sizeof(sol[0]));
		sol[i][divizori[i]] = i;
	}

	FILE *fi = fopen("divprim.in", "r");
	fscanf(fi, "%d", &T);
	FILE *fo = fopen("divprim.out", "w");
	while (T--) {
		fscanf(fi, "%d %d", &N, &K);
		//printf("%d %d\n", N, K);
		fprintf(fo, "%d\n", sol[N][K]);
	}
	fclose(fo);
	fclose(fi);

	return 0;
}