#include<stdio.h>
using namespace std;
#define dim  1000000

short int v[dim];

int main()
{int i,j,n,t,k;
	
FILE *f=fopen("divprim.in","r"), *g=fopen("divprim.out","w");
fscanf(f,"%d",&t);
for(i=3;i<=dim/2;i+=2)
	if(v[i]==0)
		{
			for(j=2;j*i<=dim;j++)
			v[i*j]++;
		}

for(i=1;i<=t;i++)
{
	fscanf(f,"%d%d",&n,&k);
	for(j=n;j>=1;j--)
		if(j%2==0)
			{if(v[j]+1==k) { fprintf(g,"%d\n",j);break;}}			
		else if(v[j]==k) { fprintf(g,"%d\n",j);break;}
		
		if(j==0)
		fprintf(g,"0\n");
}
fclose(f);
fclose(g);

return 0;
}