#include <stdio.h>

#define MAXn 1000000

int n, k, c [MAXn+5], a [9] [MAXn+5];


void ciur ()
{
	int i, j;
	for (i=2; i<=MAXn; ++i)
		if (c [i] == 0)
			for (j=i; j<=MAXn; j+=i)
				++c [j];
}

void constr_mat ()
{
	int i;
	for (i=1; i<=MAXn; ++i)
		if (c [i] <= 7)
			a [c [i]] [++a [c [i]] [0]]=i;
}

int bs ()
{
	int step, i;
	for (step=1; step<=a [k] [0]; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=a [k] [0] && a [k] [i+step]<=n)
			i+=step;
	if (i == 0 || a [k] [i] > n)
		return 0;
	return a [k] [i];
}

 int main ()
{
	freopen ("divprim.in", "r", stdin);
	freopen ("divprim.out", "w", stdout);
	int t, i;
	ciur ();
	constr_mat ();
	scanf ("%d", &t);
	for (i=1; i<=t; ++i)
	{
		scanf ("%d %d", &n, &k);
		printf ("%d\n", bs ());
	}
	return 0;
}