#include<cstdio>
#include<vector>
using namespace std;

int divPrimi[1000001];
vector <int> Idiv[8];

void NumaraDivPrimi(){

	int i, j;
	for (i = 2; i <= 1000000; i++)
		if (divPrimi[i] == 0)
			for (j = i; j <= 1000000; j += i) divPrimi[j]++;
	
	for (i = 2; i <= 1000000; i++)
		if (1 <= divPrimi[i] && divPrimi[i] <= 7)
			Idiv[divPrimi[i]].push_back(i);
}

int CautaBinar(int nr, int nrDiv){
	int st = 0, dr = Idiv[nrDiv].size() - 1, m;
	
	while (st <= dr){
		m = (st + dr) / 2;
		if (Idiv[nrDiv][m] <= nr && (m + 1 > Idiv[nrDiv].size() - 1 || Idiv[nrDiv][m + 1] > nr)) return Idiv[nrDiv][m];
		else if (Idiv[nrDiv][m] > nr) dr = m - 1;
		else st = m + 1;
	}
	
	return 0;
}
int main(){
	freopen("divprim.in", "r", stdin), freopen("divprim.out", "w", stdout);
	int T, x, nrDiv, i;
	scanf ("%d", &T);
	
	NumaraDivPrimi();
	for (i = 0; i < T; i++){
		scanf ("%d %d", &x, &nrDiv);
		printf("%d\n", CautaBinar(x, nrDiv));
	}
	return 0;
}