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

bool prim[nmax];

int ok ( 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 1;
	return 0;
}

void solve ()
{
	int i, n, k;
	scanf("%d %d ", &n, &k);
	for (i = n; i >= 0; --i)
		if ( ok (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; ++i) prim[i] = true;
	prim[1] = false;
	for (i = 2; i <= nmax; ++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;
}