#include <stdio.h>
using namespace std;
#define nmax 1000005
#define pt(i) (1<<(i))

bool prim[nmax];

int nrdivizori ( int x, int k )
{
	int i, nrdiv = 0;
	for (i = 1; i <= x; ++i)
		if ( prim[i] && x % i == 0)
		{
			nrdiv ++;
			if (nrdiv > k) return 0;
		}
	if ( nrdiv == k) return 1;
	return 0;
}

void solve ()
{
	int i, n, k;
	scanf("%d %d ", &n, &k);
	for (i = n; i >= 0; --i)
		if ( nrdivizori (i, k) )
		{
			printf("%d\n", i);
			return;
		}
	printf("0\n");
}

int main ()
{
	int tcount, t, i, j;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	for (i = 2; i <= nmax-4; ++i) { prim[i] = true; if (i % 2 == 0) prim[i] = false; }
	prim[1] = false; prim[2] = true;
	for (i = 3; i <= nmax-4; ++i)
		if ( prim[i] )
			for (j = i+i; j <= nmax; j+=i)
				prim[j] = false;
	scanf("%d ", &t);
	for (tcount = 1; tcount <= t; ++tcount)
		solve ();
	return 0;
}