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

fun main() {
    val builder = StringBuilder()

    val t = readInputLine().toInt()

    val primes = listOf(2L, 3L, 5L)

    repeat(t) {
        val (n, a, b, c, d) = readInputLine().split(" ").map { it.toLong() }

        val coinMap = mapOf(2L to a, 3L to b, 5L to c)

        // value -> cost
        val costMap = mutableMapOf<Long, Long>()

        // (value, cost)
        val queue = PriorityQueue<Pair<Long, Long>> { x, y -> x.second.compareTo(y.second) }

        queue.add(Pair(n, 0L))
        costMap[n] = 0L

        var ans = 1e18.toLong()

        fun addQueue(value: Long, cost: Long) {
            if (value < n + 100L && cost < ans && cost < costMap.getOrDefault(value, 1e18.toLong())) {
                costMap[value] = cost
                queue.add(Pair(value, cost))
            }
        }

        while (queue.isNotEmpty()) {
            val (current, cost) = queue.poll()

            if (cost >= ans) {
                break
            }

            if (current <= 2e18.toLong() && cost + current * d > 0L) {
                ans = min(ans, cost + current * d)
            }

            for (p in primes) {
                val mod = current % p
                addQueue(current / p, cost + mod * d + coinMap[p]!!)
                addQueue(current / p + 1L, cost + (p - mod) * d + coinMap[p]!!)
            }
        }

        builder.appendln(ans)
    }

    print(builder.toString())
}

fun readInputLine(): String {
    return readLine()!!
}
