import java.util.*
import kotlin.math.cos

private class A {



    fun solve() {
        var t = nextInt()
        while (t-- > 0) {
            val n = nextLong()
            val a = nextLong()
            val b = nextLong()
            val c = nextLong()
            val d = nextLong()
            println(doit(n, a, b, c, d))
        }
    }

    fun doit(n: Long, a: Long, b: Long, c: Long, d: Long): Long {
        val dp: MutableMap<Long, Long> = mutableMapOf()
        val q: PriorityQueue<QueueEntity> = PriorityQueue()
        q.add(QueueEntity(0, n))
        dp[n] = 0
        val tryAddCost: (Long, Long) -> Unit = { cost, number ->
            if (!dp.containsKey(number) || dp[number]!! > cost) {
                dp[number] = cost
                q.add(QueueEntity(cost, number))
            }
        }
        while (q.isNotEmpty()) {
            val e = q.poll()
            if (e.number == 0L) {
                break;
            }
            if (dp[e.number]!! < e.cost) {
                continue
            }
            if (e.number == 1L) {
                tryAddCost(e.cost + d, 0)
                continue
            }
            if (e.number % 2 == 0L) {
                val nextCost = e.cost + bestCost(e.number, 2, a, d)
                tryAddCost(nextCost, e.number / 2)
            } else {
                val nextCost1 = e.cost + bestCost(e.number + 1, 2, a, d) + d
                val nextCost2 = e.cost + bestCost(e.number - 1, 2, a, d) + d
                tryAddCost(nextCost1, (e.number + 1) / 2)
                tryAddCost(nextCost2, (e.number - 1) / 2)
            }

            if (e.number % 3 == 0L) {
                val nextCost = e.cost + bestCost(e.number, 3, b, d)
                tryAddCost(nextCost, e.number / 3)
            } else {
                val reminder = e.number % 3
                val nextCost1 = e.cost + bestCost(e.number - reminder + 3, 3, b, d) + d * (3 - reminder)
                val nextCost2 = e.cost + bestCost(e.number - reminder, 3, b, d) + d * reminder
                tryAddCost(nextCost1, (e.number - reminder + 3) / 3)
                tryAddCost(nextCost2, (e.number - reminder) / 3)
            }

            if (e.number % 5 == 0L) {
                val nextCost = e.cost + bestCost(e.number, 5, c, d)
                tryAddCost(nextCost,  e.number / 5)
            } else {
                val reminder = e.number % 5
                val nextCost1 = e.cost + bestCost(e.number - reminder + 5, 5, c, d) + d * (5 - reminder)
                val nextCost2 = e.cost + bestCost(e.number - reminder, 5, c, d) + d * reminder
                tryAddCost(nextCost1, (e.number - reminder + 5) / 5)
                tryAddCost(nextCost2, (e.number - reminder) / 5)
            }

        }
        return dp[0]!!
    }

    class QueueEntity(val cost: Long, val number: Long): Comparable<QueueEntity> {
        override fun compareTo(other: QueueEntity): Int {
            if (cost == other.cost) {
                return number.compareTo(other.number)
            }
            return cost.compareTo(other.cost)
        }
    }

    fun bestCost(n: Long, divider: Int, divideCost: Long, minusCost: Long): Long {
        val count = n - (n / divider)
        if (count <= 1000000000) {
            return Math.min(divideCost, minusCost * count)
        } else {
            return divideCost
        }
    }

    var tokenBuffer = listOf<String>()
    var bufferPosition = 0

    private fun checkBuffer() {
        if (bufferPosition == tokenBuffer.size) {
            tokenBuffer = nextLine().split(" ")
            bufferPosition = 0
        }
    }

    fun nextLine() = readLine()!!
    fun nextInt(): Int {
        checkBuffer()
        return tokenBuffer[bufferPosition++].toInt()
    }

    fun nextLong(): Long {
        checkBuffer()
        return tokenBuffer[bufferPosition++].toLong()
    }

    fun nextDouble(): Double {
        checkBuffer()
        return tokenBuffer[bufferPosition++].toDouble()
    }

    fun nextToken(): String {
        checkBuffer()
        return tokenBuffer[bufferPosition++]
    }
}

fun main() {
    val reader = A().solve()

}


Measured memory_bytes: 55836