#include <cstdio>

int nrprim(int y)
{
	int nr=0;
	if (y%2==0)
	{
		nr++;
		while (y%2==0)
			y/=2;
	}
    for (int i=3;i*i<=y;i+=2)
		if (y%i==0)
		{
			nr++;
			while (y%i==0)
				y=y/i;
		}
	if (y!=1) nr++;
	return nr;
}


int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,n,k;
	scanf("%d",&t);
	for (int i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&k);
		int nr=0;
		for (int j=n;j>=2;j--)
			if (nrprim(j)==k)
			{
				printf("%d\n",j);
				nr=j;
				break;
			}
		if (nr==0)
			printf("0\n");
	}
	return 0;
}