#include <stdio.h>
#include <math.h>
void prime(unsigned long n, unsigned long *h1, unsigned long *h2, unsigned long *h3){
  unsigned long tn = n;
   while(1){
    if(tn%5!=0){
      tn = n;
      break;
    }else{
      tn=tn/5;
      *h1 = *h1 + 1;
    }
   }
   while(1){
    if(tn%3!=0){
      tn = n;
      break;
    }else{
      tn=tn/3;
      *h2 = *h2 + 1;
    }
   }
   while(1){
    if(tn%2!=0){
      tn = n;
      break;
    }else{
      tn = tn/2;
      *h3 = *h3 + 1;
    }
   }
}

int main(void){
  int t;
  unsigned long a,b,c,d,have=0,h1=0,h2=0,h3=0;
  unsigned long n,ans1,ans2=2061584302,tn;
  scanf("%d", &t);
  for(int i=0;i<t;i++){
    scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);
    unsigned long m = 2*n;
    unsigned long ans[m];
    ans1 = d;
    tn=n;
    for(int j=0;j<n;j++){
      ans[j]=j*d;
      prime(tn, &h1, &h2, &h3);
    //  printf("%d %d %d\n", h1, h2, h3);
      unsigned long co=1;
      for(int k=0;k<h1;k++){
        co=co*5;
        //printf("%d\n", co);
      }
      for(int k=0;k<h2;k++){
        co=co*3;
      //  printf("%d\n", co);
      }
      for(int k=0;k<h3;k++){
        co=co*2;
      }
    //  printf("%d\n", co);
      if(co==tn){
        ans[j]=ans[j]+c*h1+b*h2+a*h3;
      }else{
        ans[j]=0;
      }
      tn = tn-1;
      //  printf("%d\n", ans[j]);
      h1=h2=h3=0;
    }
    tn = n;
    for(int j=n;j<m;j++){
      ans[j]=(j-n)*d;
      prime(tn, &h1, &h2, &h3);
    //  printf("%d %d %d\n", h1, h2, h3);
      unsigned long co=1;
      for(int k=0;k<h1;k++){
        co=co*5;
        //printf("%d\n", co);
      }
      for(int k=0;k<h2;k++){
        co=co*3;
      //  printf("%d\n", co);
      }
      for(int k=0;k<h3;k++){
        co=co*2;
      }
    //  printf("%d\n", co);
      if(co==tn){
        ans[j]=ans[j]+c*h1+b*h2+a*h3;
      }else{
        ans[j]=0;
      }
      tn = tn+1;
      //printf("%d\n", ans[j]);
      h1=h2=h3=0;
    }
    for(int j=0;j<2*n;j++){
      if(ans2>ans[j] && ans[j]!=0){
        ans2 = ans[j];
      }
    }
    tn = n;
    unsigned long ans3=0,ans4=0;
    while(1){
    if(tn%2==0){
      tn = tn/2;
      ans3=ans3+a;
    }else
    if(tn%3==0){
      tn = tn/3;
      ans3=ans3+b;
    }else
    if(tn%5==0){
      tn = tn/5;
      ans3=ans3+c;
    }else{
      tn=tn-1;
      ans3 = ans3 + d;
    }
  //  printf("%d %d\n", tn, ans3);
    if(tn == 1){
      break;
    }
  }
  tn = n;
  while(1){
  if(tn%2==0){
    tn = tn/2;
    ans4=ans4+a;
  }else
  if(tn%3==0){
    tn = tn/3;
    tn = tn + 1;
    ans4=ans4+b;
  }else
  if(tn%5==0){
    tn = tn/5;
    tn = tn + 1;
    ans4=ans4+c;
  }else{
    tn=tn+1;
    ans4 = ans4 + d;
  }
//  printf("%d %d\n", tn, ans4);
  if(tn == 1){
    break;
  }

}
    if(ans2<ans4&&ans2<ans3){
    ans1 = ans1 + ans2;
  }
  if(ans3<ans2&&ans3<ans4){
    ans1 = ans1 + ans3;
  }
  if(ans4<ans2&&ans4<ans3){
    ans1 = ans1 + ans4;
  }
    printf("%d\n", ans1);
    ans1=0;ans2=0;
 }
 return 0;
}