#include <stdio.h>
#include <stdlib.h>
#define NMAX 1000000

int ciur[NMAX+1],kmin[7];
int main(){
  int d,i,t,k,n,j;
  FILE *fin, *fout;

  ciur[1]=0;
  for(d=2;d<=NMAX;d++){
    if(ciur[d]==0)
      for(i=d;i<=NMAX;i+=d)
        ciur[i]++;
    else if(kmin[ciur[d]]==0)
      kmin[ciur[d]]=d;
  }

  fin=fopen("divprim.in","r");
  fout=fopen("divprim.out","w");
  fscanf(fin,"%d",&t);
  for(i=0;i<t;i++){
    fscanf(fin,"%d%d",&n,&k);
    j=n;
    if(kmin[k]>n)
      fprintf(fout,"0\n");
    else{
      while(ciur[j]!=k)
        j--;
      fprintf(fout,"%d\n",j);
    }
  }
  fclose(fin);
  fclose(fout);
  return 0;
}