#include <stdio.h>
#include <stdlib.h>
int c[1000005];

int main()
{
    FILE *fin, *fout;
    int i,j,k,n,t;
    for(i=2;i<=1000000;i=i+2)
      ++c[i];
    for(i=3;i<=1000000;i=i+2)
      if(c[i]==0)
        for(j=i;j<=1000000;j=j+i)
          ++c[j];
    fin=fopen("divprim.in","r");
    fscanf(fin,"%d",&t);
    fout=fopen("divprim.out","w");
    for(i=0;i<t;++i){
      fscanf(fin,"%d%d",&n,&k);
      while(n>0&&c[n]!=k){
        n--;
      }
      fprintf(fout,"%d\n",n);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}