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

fun main() {

    val coins = arrayOf(2L,3L,5L) //61, 39, 27

    val sc = Scanner(System.`in`)
    val t = sc.nextInt()

    repeat(t) {
        val n = sc.nextLong()
        val costs = LongArray(3)
        costs[0] = sc.nextLong()
        costs[1] = sc.nextLong()
        costs[2] = sc.nextLong()
        val d = sc.nextLong()

        val cache = HashMap<Long,Long>()

        fun bestCost(v:Long, c:Int, p : Long, r:Long): Long {
            if(p == 0L){
                return r * d
            }
            val remainder = r * d
            val cost = costs[c] + remainder
            val diff = v - p
           // val costD = diff * d
            val b1 = BigInteger(cost.toString())
            val b2 = BigInteger(diff.toString()).multiply(BigInteger(d.toString()))
            if(b1 < b2) {
                return b1.toLong()
            } else {
                return b2.toLong()
            }
//            if(costD < 0)
//                return cost
//            return min(costD, cost)
        }

        fun solve(remain:Long): Long {
            if(remain == 0L)
                return 0L
            if(remain == 1L)
                 return d
            if(cache.contains(remain)) {
                return cache[remain]!!
            }
            var best = Long.MAX_VALUE
            for(i in coins.indices) {
                val c = coins[i]
                val p = remain / c
                val r = remain % c
                val up = p + 1L
                val ur = c - r
                best = min(best, bestCost(remain, i, p, r) + solve(p))
                if(ur == c) {
                    continue
                }
                best = min(best, bestCost(remain, i, up, ur) + solve(up))
            }
            cache[remain] = best
            return best
        }
        println(solve(n))

        // 0x1000 - 1
        // 0x0fff
        // 2^n
        // 0x1024 - 1
        // 0x100000
        // 0x0fffff & 0x03424
        //
    }


}