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