#include<stdio.h>
long int i,a[1000001],j,min[8],t,n,k;
int main()
{
	FILE *f,*g;
	f=fopen("divprim.in","r");
	g=fopen("divprim.out","w");
	a[1000000]=2;
	a[999999]=5;
	for(i=2;i<=999998;i++)
	 if(!a[i])
	  for(j=i;j<=999998;j=j+i)
	   a[j]++;
	min[0]=1;min[1]=2;min[2]=min[1]*3;min[3]=min[2]*5;
	min[4]=min[3]*7;min[5]=min[4]*11;min[6]=min[5]*13;min[7]=min[6]*17;
	fscanf(f,"%ld",&t);
	for(i=1;i<=t;i++)
	{
		fscanf(f,"%ld%ld",&n,&k);
		if(k>=1)
		{ if(n>=min[k])
		   {
		     for(j=n;j>=0;j--)
		     if(a[j]==k) break;
		     fprintf(g,"%ld\n",j);
		   }
		   else  fprintf(g,"0\n");
		}
		else
		 fprintf(g,"1\n");
        }
	fcloseall();
	return 0;
}