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

int main()
{
    FILE *fin, *fout;
    int i,j,k,n,t,x;
    for(i=2;i<=1000000;i=i+2)
      ++c[i];
    c[i]=1;
    for(i=3;i<=1000000;i++)
      if(c[i]==0)
        for(j=i;j<=1000000;j=j+i)
          ++c[j];
    for(i=1;i<=7;i++){
      for(j=1;j<=1000000;j++){
        if(c[j]==i){
          a[i][j]=j;
          //printf("%d %d %d   ",c[j],a[i][j],i);
        }
        else{
          a[i][j]=a[i][j-1];
          //printf("%d %d %d\n",i,j,j-1);
         // if(a[2][0]!=0)
           // printf("%d %d\n",i,j);
          //printf("%d %d %d %d  ",a[i][j-1],a[i][j],j-1,j);
        }
      }
      //printf("\n");
    }
    //printf("%d ",a[1][10]);
    //printf("%d",a[2][0]);
    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);
      fprintf(fout,"%d\n",a[k][n]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}