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

using namespace std;

int T,
	N, K;

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

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();

	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);
		int i;
		for (i = N; i > 0; --i)
			if (divizori[i] == K)
				break;
		fprintf(fo, "%d\n", i);
	}
	fclose(fo);
	fclose(fi);

	return 0;
}