#include <stdio.h>
#define max 1000001 
int e[max];
void precalcul()
{
	int i,j;
	for (i=1; i<max; i++)
		e[i]=0;		
	for (i=2; i<=max-1; i++)
	{
		if (e[i]==0)
		for (j=i; j<=max; j+=i)
			e[j]++;
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,i,n,k,j,gasit;
	scanf("%d",&t);
	precalcul();
	for (i=1; i<=t; i++)
	{
		gasit=0;
		scanf("%d%d",&n,&k);
		for (j=n-1; j>=1; j--)
			if (e[j]==k)
			{
				printf("%d\n",j);
				gasit=1;
				break;
			}
			/*if (e[j]<k)
				gasit=0;
			else
				gasit=1;
		}*/
		if (gasit==0)
			printf("0\n");
	}
	return 0;
}