#include <bits/stdc++.h>
#define maxn 1000000
using namespace std;

int ndiv[1000005];

vector <int> vec[8];

int cautarebin(int l, int r, int x, int k) {
	if (l > r) {
		return 0;
	}
	int mid = (l + r) / 2;

	if (vec[k][mid] <= x && mid == r) {
		return vec[k][mid];
	}

	if (vec[k][mid] <= x && vec[k][mid + 1] > x) {
		return vec[k][mid];
	}

	if (vec[k][mid] <= x) {
		return cautarebin(mid + 1, r, x, k);
	}

	return cautarebin(l, mid - 1, x, k);
}


int main() {
	freopen("divprim.in", "r", stdin);
	freopen("divprim.out", "w", stdout);

	int t, n, k;
	scanf("%d", &t);

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

		if (ndiv[i]) {
                continue;
		}
			for (int j = i; j <= maxn; j += i)
                ndiv[j]++;



	}

	for (int i = 2; i <= maxn; ++i) {
		if (ndiv[i] <= 7)
			vec[ndiv[i]].push_back(i);
	}

	for (int i = 0; i < t; ++i) {

	scanf("%d %d", &n, &k);
	printf("%d\n", cautarebin(0, vec[k].size() - 1, n, k));
	}

	return 0;
}