#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
 
using namespace std;

int ndiv[1000005];

vector <int> numbers[8];

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

	if (numbers[k][mid] <= x && mid == h) {
		return numbers[k][mid];
	}

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

	if (numbers[k][mid] <= x) {
		return binSearch(mid + 1, h, x, k);
	}

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


void solve() {
	int n, k;
	scanf("%d %d", &n, &k);
	printf("%d\n", binSearch(0, numbers[k].size() - 1, n, k));
}

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

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

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

		if (ndiv[i]) {
			continue;
		}

		for (int j = i; j <= 1000000; j += i) {
			ndiv[j]++;
		}
	}

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

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

	return 0;
}