#include<stdio.h>
FILE *f=fopen("divprim.in","r"),
     *g=fopen("divprim.out","w");
long a[1000001],i,n,t,p[100001],k,ok,j,x;
int main()
{ fscanf(f,"%ld",&t);
  k=4;
  p[1]=2;
  p[2]=3;n=2;
  while(k<=1000000){ ++k;ok=1;for(i=1;i<=n&&ok;++i) if(k%p[i]==0) ok=0;if(ok) p[++n]=k;
		   }
  k=0;
  for(i=1;i<=n;++i) for(j=1;j<=1000000;++j) { x=j;k=0;if(x%p[i]==0) ++a[j];
					  }
  for(i=1;i<=t;i++) { fscanf(f,"%ld %ld",&n,&k);
		      while(a[n]!=k&&n>0) n--;
		      fprintf(g,"%ld\n",n);
		    }
  fclose(f);
  fclose(g);
  return 0;
}