using namespace std;
#include<fstream>

int nrdiv(int n)
{
	int copie=n,divpr, nr=0;
	for(divpr=2;divpr*divpr<=copie && n!=1;++divpr)
		if(n%divpr==0)
		{
			++nr;
			while(n%divpr==0)
				n/=divpr;
		}
	if(n!=1)
		++nr;
	return nr;
}

int calcul(int n, int k)
{
	for(int i=n;i;--i)
		if (nrdiv(i)==k)
			return i;
	return 0;
}

int main ()
{
	int N,K,T;
	ifstream in("divprim.in");
	ofstream out("divprim.out");
	in>>T;
	while(T--)
	{	
		in>>N>>K;
		out<<calcul(N,K)<<'\n';
	}
	in.close();out.close();
	return 0;
}