import java.lang.Math.abs
import java.math.BigInteger

fun main(args: Array<String>) {

    repeat(readLine()!!.toInt()) {
        val sp = readLine()!!.split(" ")

        val n = sp[0].toLong()
        val (a, b, c, d) = sp.drop(1).map { it.toInt() }

        val t = Task(n, a.big, b.big, c.big, d.big)

        println(t.solve(n))
        //  println(t.solutions)
    }
}

data class Task(val n: Long, val a: BigInteger, val b: BigInteger, val c: BigInteger, val d: BigInteger) {
    val solutions = mutableMapOf<Long, BigInteger>()

    var pre = false
    fun solve(n: Long): BigInteger {
        if (solutions.containsKey(n)) return solutions[n]!!

        if (n == 0L) return BigInteger.ZERO
        if (n == 1L) return d

        val variants = mutableListOf<BigInteger>()
        variants.add(n.big * d)
        for (i in -1..1) if ((n + i) > 0 && (n + i) % 2 == 0L) {
            variants.add(abs(i) * d + solve((n + i) / 2) + a)
        }

        for (i in -2..2) if ((n + i) > 0 && (n + i) % 3 == 0L) {
            variants.add(abs(i) * d + solve((n + i) / 3) + b)
        }

        for (i in -5..5) if ((n + i) > 0 && (n + i) % 5 == 0L) {
            variants.add(abs(i) * d + solve((n + i) / 5) + c)
        }


        val ans = variants.min()!!

        solutions[n] = ans
        return ans
    }


}

private val Long.big: BigInteger
    get() = BigInteger.valueOf(this)

private val Int.big: BigInteger
    get() = this.toLong().big

private operator fun Int.times(big: BigInteger): BigInteger {
    return big.multiply(this.big)
}
