#include <fstream.h>
#include <math.h>
unsigned long T, ok, n, k, j, nrdiv=0, i, m;
int main()
{
ifstream f("divprim.in");
ofstream g("divprim.out");
f>>T;
for(i=1; i<=T; i++)
    {
    f>>n>>k;
    ok=1;
    for(j=n; j>=1&&ok; j--)
	{for(m=2; m<=sqrt(j); m++)
	    {if(j%m==0)
	       nrdiv++;
	    }
	 if(nrdiv==k)
	    ok=0;
	 nrdiv=0;
	 }
    g<<j;
    }
f.close();
g.close();
return 0;
}