#include<stdio.h>
const int z=1000000;
int t,n,k,nrd[1000000];
void ciur()
{
	int j=0;
	for(int i=2;i<=z;++i)
		if(nrd[i]==0)
			for(j=i;j<=z;j+=i)
				++nrd[j];
}
int main()
{
	int nrmax=0;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	ciur();
	for(int r=1;r<=t;++r)
	{
		scanf("%d%d",&n,&k);
		for(int i=n;i>=1;--i)
		{
			if(nrd[i]==k && i>nrmax)
			{
				nrmax=i;
				break;
			}
		}
	printf("%d\n",nrmax);
	nrmax=0;
	}
	return 0;
}