import java.util.*
import kotlin.math.min

fun main(args : Array<String>) {
    val t = readLine()!!.toInt()

    repeat(t) {
        val (n, a, b, c, d) = readLine()!!.split(" ").map { it.toLong() }
        val divs = longArrayOf(2L, 3L, 5L)
        val costs = longArrayOf(a, b, c)

        val dfs = PriorityQueue<State>()
        dfs.add(State(n, 0))

        var seen = mutableMapOf<Long, Long>()
        seen[0] = Long.MAX_VALUE

        fun pushIfNecessary(nextNum: Long, totalCoins: Long) {
            if ((seen[nextNum] ?: Long.MAX_VALUE) <= totalCoins) return
            seen[nextNum] = totalCoins
            dfs.add(State(nextNum, totalCoins))
        }

        while (dfs.isNotEmpty()) {
            val state = dfs.poll()

            if (state.currentNum == 0L) {
                break
            }

            if ((seen[state.currentNum] ?: Long.MAX_VALUE) < state.totalCoins) {
                continue
            }

            if (state.currentNum == 1L) {
                pushIfNecessary(0, state.totalCoins+d)
                continue
            }

            (0..2).forEach { idx ->
                val div = divs[idx]
                val cost = costs[idx]

                if (state.currentNum % div == 0L) {
                    val nextCost = calcCost (state.currentNum, div, cost, d)
                    pushIfNecessary(state.currentNum/div, state.totalCoins+nextCost)
                } else {
                    val rest = state.currentNum % div
                    val nextCostF = calcCost(state.currentNum-rest, div, cost, d)
                    val nextCostC = calcCost(state.currentNum+(div-rest), div, cost, d)
                    pushIfNecessary((state.currentNum-rest)/div, state.totalCoins+nextCostF+(d*rest))
                    pushIfNecessary((state.currentNum+(div-rest))/div, state.totalCoins+nextCostC+(d*(div-rest)))
                }
            }
        }

        println(seen[0])
    }
}

data class State(val currentNum: Long, val totalCoins: Long): Comparable<State> {
    override fun compareTo(other: State): Int {
        if (totalCoins == other.totalCoins) {
            return currentNum.compareTo(other.currentNum)
        }
        return totalCoins.compareTo(other.totalCoins)
    }
}

fun calcCost(currentNum: Long, divider: Long, mCost: Long, dCost: Long): Long {
    val diff = currentNum - (currentNum/divider)
    if (diff > Int.MAX_VALUE) {
        return mCost
    } else {
        return min(diff * dCost, mCost)
    }
}