#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int v[1000],nr=0;
void ciur()
{
int i,j; 
char c[1000]={0};
for(i=2;i<=1000;i++)
	if(c[i]==0)
	{
		for(j=i*i;j<=1000;j=j+i)
			c[j]=1;
		nr=nr+1;
		v[nr]=i;
	}
};
int desc(int j)
{
	int i,r;
	r=0;
	for(i=1;v[i]<=j;i++)
		if(j%v[i]==0)
			r=r+1;
return r;
};
int main()
{
	int n,k,t,i,j;
	cin>>t;
	ciur();
	for(i=1;i<=t;i++)
	{
		cin>>n;
		cin>>k;
		for(j=n;j>=2;j=j-1)
			if(desc(j)==k)
			{
				cout<<j<<"\n";
				j=0;
			}
	if(j==1)
		cout<<"0 \n";
	}
return 0;
}