#include <fstream>
#include <cstring>
#include <vector>

#define MAX_N 1000005
#define MAX_K 10

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int T, N, K, D[MAX_N];
bool prim[MAX_N];

vector<int> P[MAX_K];

void ciur()
{
	memset (prim, true, sizeof(prim));
	
	for (int i = 2; i <= MAX_N; i++)
		if (prim[i]) {
			D[i] = 1;
			for (int j = 2 * i; j <= MAX_N; j += i) {
				prim[j] = false;
				D[j]++;
			}
		}
}

void precompute()
{
	for (int i = 1; i <= MAX_N; i++)
		P[D[i]].push_back(i);
}

int bsearch()
{
	int lo = 1, hi = P[K].size(), mid;
	
	while (lo <= hi) {
		mid = (lo + hi) / 2;
		if (P[K][mid - 1] <= N)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	
	if (P[K][mid - 1] > N)
		mid--;
	if (P[K][mid - 1] <= N && mid > 0)
		return P[K][mid - 1];
	else
		return 0;
}

int main()
{
	ciur();
	precompute();
	
	f >> T;
	while (T--) {
		f >> N >> K;
		g << bsearch() << '\n';
	}
	
	f.close();
	g.close();
	
	return 0;
}