#include <iostream>

using namespace std;

#define maxN 1000005


int nrdiv[maxN], rsp[maxN][10];


int main()
{
	freopen ("divprim.in", "r", stdin);
	freopen ("divprim.out", "w", stdout);
	
	int T;
	
	scanf ("%d", &T);
	
	rsp[1][0] = 1;
	
	for (int i = 2; i < maxN; ++ i)
	{
		if ( ! nrdiv[i] )
			for (int j = i; j < maxN; j += i)
				++ nrdiv[j];
		
		for (int t = 0; t <= 7; ++ t)
			rsp[i][t] = rsp[i - 1][t];
		
		if (nrdiv[i] <= 7)
			rsp[i][nrdiv[i]] = i;
	}
	
	
	while (T --)
	{
		int N, K;
		
		scanf ("%d %d", &N, &K);
		
		printf ("%d\n", rsp[N][K]);
	}
	
	return 0;
}