#include<stdio.h>
const int N=(1<<20);
int nr[8],nrdiv[N],a[8][N/2];

int caut(int n,int v[],int k)
{
	int i,pas=(1<<17);
	for(i=0;pas!=0;pas>>=1)
		if(i+pas<nr[k] && v[i+pas]<=n)
			i+=pas;
	if(i==0)
		return 0;
	return v[i];
}	
int main()
{
	int i,n,k,t,x,d,j;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	for(i=2;i<N;i++)
	{	
		if(nrdiv[i]==0)
		{
			for(j=i;j<N;j+=i)
				nrdiv[j]++;
		}
	}
	a[0][1]=1;
	nr[0]=1;
	for(i=2;i<N;++i)
	{
		//il adaug pe i pe linia nrdiv[i] a matricei
		d=nrdiv[i];
		x=++nr[d];
		a[d][x]=i;
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",caut(n,a[k],k));
	}
	return 0;
}