using namespace std;
#include<fstream>
#include<vector>

const int NP=1005;

int prime[NP];

void precalcul()
{
	int i,j;
	bool v[NP]={false};
	for(i=2;i*i<NP;++i)
		if(!(v[i]))
			for(j=i*i;j<NP;j+=i)
				v[j]=true;
	for (i=2;i<NP;i++)
		if(!v[i])
			prime[++prime[0]]=i;
}

int nrdiv(int n)
{
	int copie=n,i, nr=0;
	for(i=1;prime[i]*prime[i]<=copie && n!=1;++i)
		if(n%prime[i]==0)
		{
			++nr;
			while(n%prime[i]==0)
				n/=prime[i];
		}
	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");
	precalcul();
	in>>T;
	while(T--)
	{	
		in>>N>>K;
		out<<calcul(N,K)<<'\n';
	}
	in.close();out.close();
	return 0;
}