function exec(N, A, B, C, D) {
  // console.log(N, A, B, C, D)

  // 
  let queue = [
    {
      c: 0n,
      n: N,
      // debug
      d: 0
    }
  ]
  let visited = {
  }
  let min = Number.MAX_SAFE_INTEGER

  while(queue.length > 0) {
    const q = queue.shift()
    // console.log(q.d, q, 'remain:', queue.length, 'min:', min)
    // console.log(queue)

    // // debug
    // if (q.d > 2) break

    visited[q.n] = q.c
    // クリア判定
    if (0n === q.n) {
      // console.log('found:', q)
      if (min > q.c) {
        min = q.c
        continue
      }
    }

    // 終了判定
    if (min <= q.c) {
      // console.log('finish')
      continue
    }

    //A
    if (q.n % 2n === 0n) {
      const n = q.n / 2n
      const cD = q.c + A
      const cA = q.c + D * (q.n - n)
      if (!visited[n] || visited[n] > cD || visited[n] > cA) {
        if (cD < cA) {
          visited[n] = cD
          queue.push({
            c: cD,
            n: n,
            d: q.d+1
          })
        } else {
          visited[n] = cA
          queue.push({
            c: cA,
            n: n,
            d: q.d+1
          })
        }
      }
    } else {
      {
        const n =(q.n+1n) / 2n
        const cD = q.c + A + D
        const cA = q.c + D * (q.n - n)
        if (!visited[n] || visited[n] > cD || visited[n] > cA) {
          if (cD < cA) {
            visited[n] = cD
            queue.push({
              c: cD,
              n: n,
              d: q.d+1
            })
          } else {
            visited[n] = cA
            queue.push({
              c: cA,
              n: n,
              d: q.d+1
            })
          }
        }
      }
      {
        const n = (q.n-1n) / 2n
        const cD = q.c + A + D
        const cA = q.c + D * (q.n - n)
        if (!visited[n] || visited[n] > cD || visited[n] > cA) {
          if (cD < cA) {
            visited[n] = cD
            queue.push({
              c: cD,
              n: n,
              d: q.d+1
            })
          } else {
            visited[n] = cA
            queue.push({
              c: cA,
              n: n,
              d: q.d+1
            })
          }
        }
      }
    }
    //B
    if (q.n % 3n === 0n) {
      const n = q.n / 3n
      const cD = q.c + B
      const cA = q.c + D * (q.n - n)
      if (!visited[n] || visited[n] > cD || visited[n] > cA) {
        if (cD < cA) {
          visited[n] = cD
          queue.push({
            c: cD,
            n: n,
            d: q.d+1
          })
        } else {
          visited[n] = cA
          queue.push({
            c: cA,
            n: n,
            d: q.d+1
          })
        }
      }
    } else {
      {
        const upDistance = (3n - q.n % 3n)
        let up =  upDistance + q.n

        const n = up / 3n
        const cD = q.c + B + D * upDistance
        const cA = q.c + D * (q.n - n)
        if (!visited[n] || visited[n] > cD || visited[n] > cA) {
          if (cD < cA) {
            visited[n] = cD
            queue.push({
              c: cD,
              n: n,
              d: q.d+1
            })
          } else {
            visited[n] = cA
            queue.push({
              c: cA,
              n: n,
              d: q.d+1
            })
          }
        }
      }

      {
        const downDistance = (q.n % 3n)
        const down = q.n - downDistance
        const n = down / 3n
        const cD = q.c + B + D * downDistance
        const cA = q.c + D * (q.n - n)
        if (!visited[n] || visited[n] > cD || visited[n] > cA) {
          if (cD < cA) {
            visited[n] = cD
            queue.push({
              c: cD,
              n: n,
              d: q.d+1
            })
          } else {
            visited[n] = cA
            queue.push({
              c: cA,
              n: n,
              d: q.d+1
            })
          }
        }
      }
    }
    //C
    if (q.n % 5n === 0n) {
      const n = q.n / 5n
      const cD = q.c + C
      const cA = q.c + D * (q.n - n)
      if (!visited[n] || visited[n] > cD || visited[n] > cA) {
        if (cD < cA) {
          visited[n] = cD
          queue.push({
            c: cD,
            n: n,
            d: q.d+1
          })
        } else {
          visited[n] = cA
          queue.push({
            c: cA,
            n: n,
            d: q.d+1
          })
        }
      }
    } else {
      {
        const upDistance = (5n - q.n % 5n)
        let up =  upDistance + q.n

        const n = up / 5n
        const cD = q.c + C + D * upDistance
        const cA = q.c + D * (q.n - n)
        if (!visited[n] || visited[n] > cD || visited[n] > cA) {
          if (cD < cA) {
            visited[n] = cD
            queue.push({
              c: cD,
              n: n,
              d: q.d+1
            })
          } else {
            visited[n] = cA
            queue.push({
              c: cA,
              n: n,
              d: q.d+1
            })
          }
        }
      }

      {
        const downDistance = (q.n % 5n)
        const down = q.n - downDistance
        const n = down / 5n
        const cD = q.c + C + D * downDistance
        const cA = q.c + D * (q.n - n)
        if (!visited[n] || visited[n] > cD || visited[n] > cA) {
          if (cD < cA) {
            visited[n] = cD
            queue.push({
              c: cD,
              n: n,
              d: q.d+1
            })
          } else {
            visited[n] = cA
            queue.push({
              c: cA,
              n: n,
              d: q.d+1
            })
          }
        }
      }
    }

    // queue.push({
    //   c: q.c + D,
    //   n: q.n + 1n,
    //   d: q.d+1
    // })
    // queue.push({
    //   c: q.c + D,
    //   n: q.n - 1n,
    //   d: q.d+1
    // })
    if (q.n === 1n) {
      // console.log('found next:', q.c + D)
      queue.push({
        c: q.c + D,
        n: 0n,
        d: q.d+1
      })
    }
    // console.log('visited:', visited)
  }
  return String(min)
}

function main(input) {
  const inputs = input.split('\n')
  const T = Number(inputs[0])
  for(let i = 0; i < T; i++) {
    const [N, A, B, C, D] = inputs[i + 1].split(' ').map(BigInt)
    const r = exec(N, A, B, C,D)
    console.log(r)
  }
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));
