#include <fstream>

#define MAX 1000001

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);


	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];

		
	in >> t;
	while (t){
		in >> n >> m;
		out << divizori[m][n] << '\n';
		t--;
	}
	
}