#include<stdio.h>
int n,k,t;
void calcul()
{
	int i=0,j=0,p=0,r=0,nrdiv=1,nrmax=0;
	bool ok=true;
	for(i=0;i<t;++i)
	{
		scanf("%d%d",&n,&k);
		for(j=3;j<=n;++j)
		{
			for(p=2;p*p<=j;++p)
			{
				for(r=2;r*r<=p && ok!=false;++r)
				{
					if(p%r!=0)
						ok=true;
					else ok=false;
				}
				if(ok==true && j%p==0)
				{
					if(p*p==j)
						{
							nrdiv++;
							break;
						}
					nrdiv=nrdiv+2;
				}
				ok=true;
			}
			if(nrdiv==k && nrmax<j)
				nrmax=j;
			nrdiv=0;
		}
		printf("%d\n",nrmax);
		nrmax=0;
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	calcul();
	return 0;
}