#include<stdio.h>

#define N 1000000

int i,j,n,k,a[1000002],t,aux,max[1000001][8],Max[8];

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	
	scanf("%d",&t);
	
	a[2]=1;
	
	aux=N/2;
	
	for(i=2;i<=aux;i++)
		if(a[i])
			a[i*2]=1;
	
	for(i=3;i<=N;i+=2)
		if(!a[i])
		{
			a[i]=1;
			for(j=2;j*i<=N&&j<=N;j++)
				if(!a[i*j]&&a[j])
				{
					if(j%i)
						a[i*j]=a[i]+a[j];
					else
						a[i*j]=a[j];
				}
		}
		
	for(i=1;i<=N;i++)
		if(a[i]<=7)
		{
			if(Max[a[i]]<i)
				Max[a[i]]=i;
			
			for(j=0;j<=7;j++)
				max[i][j]=Max[j];
		}	

	for(;t;t--)
	{
		scanf("%d %d",&n,&k);
		
		printf("%d\n",max[n][k]);
	}

		return 0;
}