#include <fstream>
#include <vector>


using namespace std;


ifstream cin("divprim.in");
ofstream cout("divprim.out");


const int NMAX = 1e6;


vector <int> primes[8];
int query, ciur[NMAX + 1];


int binary_search(int n, int k) {
	int left = 0, right = primes[k].size() - 1, middle, position = -1;
	while (left <= right) {
		middle = (left + right) / 2;
		if (primes[k][middle] <= n) {
			position = middle;
			left = middle + 1;
			continue;
		}
		right = middle - 1;
	}


	return (position == -1 ? 0 : primes[k][position]);
}


void eratosthenes() {
	for (int index = 2; index <= NMAX; index += 2) {
		ciur[index] = 1;
	}
	for (int index1 = 3; index1 <= NMAX; index1 += 2) {
		if (ciur[index1] == 0) {
			for (int index2 = index1; index2 <= NMAX; index2 += index1) {
				++ciur[index2];
			}
		}
	}
}


void addPrimes() {
	for (int index = 1; index <= NMAX; ++index) {
		primes[ciur[index]].push_back(index);
	}
}


void read() {
	cin >> query;
}


void solve() {
	int n, k;


	cin >> n >> k;


	cout << binary_search(n, k) << '\n';
}


int main() {
	eratosthenes();
	addPrimes();
	read();
	while (query--) {
		solve();
	}
	return 0;
}