#include<fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");

int ndiv(int x)
{
	int d=2,nr=0;
	while(x!=1 && d*d<=x)
	{
		if(x%d==0)
		{
			nr++;
			while(x%d==0)
				x/=d;
		}
		if(d==2) d++;
		else d+=2;
	}
	if(x!=1)
		nr++;
	return nr;
}

int main()
{
	int n,i,j,n2,af,k;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>n2>>k;
		af=0;
		for(j=1;j<=n2;j++)
			if(ndiv(j)==k)
				af=j;
		if(af==0)
			cout<<0<<"\n";
		else
			cout<<af<<"\n";
	}
	return 0;
}