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

#define DIM 1000000

using namespace std;

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

int f[DIM + 1];

vector<int> dp[10];

int main() {

	dp[0].push_back(1);

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

		if (f[i] == 0) 
			for (int j = i; j <= DIM; j += i)
				f[j]++;

		if (f[i] <= 7)
			dp[f[i]].push_back(i);

	}

	int testCount;
	fin >> testCount;

	while (testCount--) {

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

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

			int middle = (left + right) / 2;

			if (dp[k][middle] <= n) 
				left = middle + 1;
			else
				right = middle - 1;

		}

		fout << (right < 0 ? 0 : dp[k][right]) << "\n";

	}

	return 0;

}

//Miriam e tare!