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

using namespace std;

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

int ciur[1000005];

vector<int> v[8];

int main() {

	v[0].push_back(1);

	for (int i = 2; i <= 1000000; ++i) {

		if (ciur[i] > 0) {
			if (ciur[i] < 8)
				v[ciur[i]].push_back(i);
			continue;
		}

		v[1].push_back(i);

		for (int j = i + i; j <= 1000000; j += i)
			ciur[j]++;

	}

	int testCount;
	fin >> testCount;

	while (testCount--) {

		int n, k;
		fin >> n >> k;

		int left = 0, right = v[k].size() - 1, ans = -1;
		while (left <= right) {

			int mid = (left + right) / 2;

			if (v[k][mid] <= n) {
				ans = mid;
				left = mid + 1;
			}
			else
				right = mid - 1;

		}

		fout << (ans == -1 ? 0 : v[k][ans]) << '\n';

	}

	return 0;

}

//Trust me, I'm the Doctor!