#include <stdio.h>
short c[1000001];

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