#include <fstream>
#define n 1000005
using namespace std;

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

int divprim[n];
int v[n][9]; // cel mai apropiat de [] care are [] divizori
int k;
int nr;
int main() {

	for (int i = 2; i <= n; i++) {
		if (divprim[i] == 0) {
			for (int j = 0; j <= n; j += i) {
				divprim[j] ++;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 7; j++) {
			v[i][j] = v[i - 1][j];
		}
		if (divprim[i] <= 7) {
			v[i][divprim[i]] = i;
		}

	}

	int nrtest;
	cin >> nrtest;
	for (int counter = 1; counter <= nrtest; counter++) {
		cin >> nr >> k;
		cout << v[nr][k] << "\n";
	}

	return 0;
}