#include<stdio.h>
#include<math.h>
short v[1000000];
long nr;
void ciur(long n)
{
	long i,j;
	v[0]=v[1]=1;
	for (i=4;i<=n;i=i+2)
		v[i]=1;
	for (i=3;i<=sqrt(n);i=i+2)
		if (v[i]==0)
			for (j=i*2;j<=n;j=j+i)
				v[j]=1;
}
int nrdiv(long n)
{
	long i;
	nr=0;
	for (i=2;i<=n/2;i++)
		if (v[i]==0)
			if (n%i==0)
				nr++;
	return nr;
}
int main()
{
	long t,n,i,j,ok,k;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	ciur(1000000);
	scanf("%ld",&t);
	for (i=1;i<=t;i++)
	{
		scanf("%ld %ld",&n,&k);
		ok=0;
		for (j=n;j>=2;j--)
			if (nrdiv(j)==k)
			{
				ok=1;
				printf("%ld",j);
				break;
			}
		if (ok==0)
			printf("0");
		printf("\n");
	}
}