#include<stdio.h>
#define N 1000000
char c[N];
void init(int n)
{
	int i,j;
	for (i=2;i<=n; ++i)
		if (c[i]==0)
			for (j=i;j<=n; j+=i)
				++c[j];
}
int calcul(int n, int k)
{
	int i,rez,ver=0;
	for (int i=n; i>=2; i--)
	{
		if (c[i]==k)
		{
			rez=i;
			ver=1;
			break;
		}
	}
	if (!ver) rez=0;
	return rez;
}
int main()
{
	int t,n,i,k;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	init(1000000);
	scanf("%d",&t);
	for (i=1; i<=t; i++)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",calcul(n,k));
	}
}