#include<cstdio>
using namespace std;

int divPrimi[1000001];

void NumaraDivPrimi(){
	//calculeaza nr de div primi al tuturor nr pana la 1.000.000
	
	int i, j;
	for (i = 2; i <= 1000000; i++)
		if (divPrimi[i] == 0)
			for (j = i; j <= 1000000; j += i) divPrimi[j]++;
}

int main(){
	freopen("divprim.in", "r", stdin), freopen("divprim.out", "w", stdout);
	int T, x, nrDiv, i, j;
	scanf ("%d", &T);
	
	NumaraDivPrimi();
	for (i = 0; i < T; i++){
		scanf ("%d %d", &x, &nrDiv);
		for (j = x; j >= 2; j--)
			if (divPrimi[j] == nrDiv) printf("%d\n", j), j = 0;
		if (j == 1) printf("0\n");
	}
	return 0;
}