import java.lang.StringBuilder
import kotlin.math.min
import kotlin.system.exitProcess

fun readInt(): Int {
    var digit = System.`in`.read()
    while(digit <= 32) {
        digit = System.`in`.read()
    }

    val negative = digit == '-'.toInt()
    if (negative) {
        digit = System.`in`.read()
    }
    var res = 0
    while (digit in '0'.toInt()..'9'.toInt()) {
        res *= 10
        res += digit - '0'.toInt()
        digit = System.`in`.read()
    }
    return if (negative) -res else res
}

fun main() {
    val t = readLine()!!.toInt()

    for(testNumber in 1..t) {
        val (n, a, b, c, d) = readLine()!!.split(" ").map { it.toLong() }
        val cost = HashMap<Long, Long>()

        val ops = arrayOf(Pair(2, a), Pair(3, b), Pair(5, c))

        fun getCost(x : Long) : Long {
            if(x == 0L) return 0L
            if(cost.containsKey(x)) return cost[x]!!

            var res = if(x <= 2000000000) x * d else -1L
            for((q, cst) in ops) {
                val r = x % q
                var curr = r * d + cst + getCost(x / q)
                if(x / q + 1 < x) {
                    curr = min(curr, (q - r) * d + cst + getCost(x / q + 1))
                }
                if(res == -1L || res > curr) res = curr
            }

            cost[x] = res
            return res
        }

        println(getCost(n))
    }
}