#include <stdio.h>
#define min(x, y) ((x)>(y) ? (y) : (x))
#define abs(x) ((x)<0 ? -(x) : (x))

long ans = 1000000000000000000;
long n, a, b, c, d;

void dfs(long num, long coins, int flag){
  if(flag){
    coins = coins + abs(num - n) * d;
    ans = min(ans, coins);
    return;
  }

  dfs(num*2, coins+a, (num*2 >= n));
  dfs(num*3, coins+b, (num*3 >= n));
  dfs(num*5, coins+c, (num*5 >= n));
  dfs(num+1, coins+d, (num+1 >= n));
}

int main(){
  int t;  scanf("%d", &t);

  for(int i=0; i<t; i++){
    scanf("%ld %ld %ld %ld %ld", &n, &a, &b, &c, &d);
    long num = 1, coins = d;
    while(n / num > 125){
      num *= 5;
      coins += a;
    }
    dfs(num, coins, (1 >= n));
    printf("%ld\n", ans);
    ans = 1000000000000000000;
  }
  return 0;
}
