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

int main()
{
    FILE *fin, *fout;
    int i,j,k,n,t,x;
    for(i=2;i<=1000000;i=i+2)
      ++c[i];
    for(i=3;i<=500000;i=i+2){
      if(c[i]==0){
        for(j=i;j<=1000000;j=j+i)
          ++c[j];
      }
    }
    for(i=501000;i<=1000000;i++)
      if(c[i]==0)
        c[i]=1;
    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;
}