#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<=500000;i++)
		if(c[i]==0)
		{
			for(j=i*i;j<=500000;j=j+i)
				c[i]=1;
			nr=nr+1;
			v[nr]=i;
		}
};*/
int desc(int j)
{
	int i,r,n;
	r=j;
	n=0;
	for(i=2;i<=r;i++)
		if(r%i==0)
		{
			n=n+1;
			while(r%i==0)
				r=r/i;
		}
	if(r!=1)
		n=n+1;
	return n;
};
int main()
{
	int n,t,k,i,j;
	cin>>t;
	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;
}