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

int ciur[NMAX+1];
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]++;
  }

  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;
    while(ciur[j]!=k&&j>0)
      j--;
    fprintf(fout,"%d\n",j);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}