#include <cstdio>
#include <cstring>

#define file_in "divprim.in"
#define file_out "divprim.out"

int prim[100010],i,j,k,K,nrk,N,T,p[10000],nrp;

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &T);
	
	memset(prim,0,sizeof(prim));
	for (i=2;i<=9000;++i)
	{
		if (!prim[i])
		{
			for (j=i*2;j<=9000;j+=i)
			prim[j]=1;
		}
	}
	
	nrp=0;
	for (i=2;i<=9000;++i)
		 if (!prim[i])
			 p[++nrp]=i;
	
	/*for (i=1;i<=nrp;++i)
	     printf("%d ", p[i]);*/
		 
	while(T--)
	{
		scanf("%d %d", &N, &K);
		int okk=0;
		
		for (i=N;i>=1 && !okk;--i)
		{
			int x=i;
			nrk=0;
			int ok=1;
			for (j=1;j<=nrp && ok;++j)
			if (p[j]<x)
			{
				if (x%p[j]==0)
					 nrk++;
				if (nrk>K)
					ok=0;
			}
			
			if (nrk==K)
			{
				printf("%d\n", i);
				okk=1;
			}
		}
		
		if (!okk) 
			printf("0\n");
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}