#include <stdio.h>

#define Nmax 1000000
#define pr(x) fprintf(stderr, #x" = %d\n", x)


int nrdiv, nr, c [Nmax+5], a [9] [Nmax+1];


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

void constr_a ()
{
	int i;
	for (i=1; i<=Nmax; ++i)
	{
                if (c [i] < 8)
			a [c [i]] [++a [c [i]] [0]]=i;
	}
		
}

int bs ()
{
     int i, s;
     for (s=1; s<=a [nrdiv] [0]; s<<=1);
     for (i=0; s; s>>=1)
	     if (i+s<=a [nrdiv] [0] && a [nrdiv] [i+s] <= nr)
		     i+=s;
     if (a [nrdiv] [i] > nr)
	     return 0;
     return a [nrdiv] [i];
}

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