#include <fstream>
#include <queue>

#define MAX 1000002

using namespace std;

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

int n, m, t, ciur[MAX], divizori[8][MAX];

int main() {
	ios_base::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> t;

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

	for (int i = 2; i <= MAX; i++) divizori[ciur[i]][i] = i;
	for (int i = 1; i <= 7; i++) {
		for (int j = 2; j <= MAX; j++) {
			if (divizori[i][j] == 0)divizori[i][j] = divizori[i][j - 1];
		}
	}
		
		for (int k = 0; k < t; k++) {
			in >> n >> m;
			out << divizori[m][n] << '\n';
		}

	
	
}