fs = require('fs');
input = fs.readFileSync('/dev/stdin','utf-8');
tmp1 = input.split('\n');
T = tmp1[0];
for(i = 1;i <= 3; i++) {
  tmp2 = tmp1[i].split(' ')
  N = parseInt(tmp2[0],10);
  A = parseInt(tmp2[1],10);
  B = parseInt(tmp2[2],10);
  C = parseInt(tmp2[3],10);
  D = parseInt(tmp2[4],10);
  R = 0;
  ab(N,0);
  console.log(R);
}
function ab(n,coin) {
  
  P1 = n % 2;  P2  = (n - P1) / 2;
  tc = coin + A + D * P1;
  if(P1 == 0) { tc = coin + A * P2 + D * P1; P2 = 1; }
  if(P2 != 0) {
    if(P2 != 1) {
      ab(P2,tc);
    } else if(R == 0 || R > tc + D) R = tc + D;
  }
  if(P1 != 0) {
    P2 = P2 + 1; P1 = P2 * 2 - n;
    tc = coin + A + D * P1;
    if(P1 == 0) { tc = coin + A * P2 + D * P1; P2 = 1; }
    if(P2 != 0) {
      if(P2 != 1) {
        ab(P2,tc);
      } else if(R == 0 || R > tc + D) R = tc + D;
    }
  }




}