import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  val T = sc.nextInt

  for (i <- 1 to T) {
    val N = sc.nextLong
    val A, B, C, D = sc.nextInt

    val dp = Array.fill((N / 10e9 + 1).toInt, 10e9.toInt)(Int.MaxValue)

    dp(0)(0) = 0
    for (i <- 0L until N) {
      def i1(x: Long = i): Int = (x / 10e9).toInt
      def i2(x: Long = i): Int = (x % 10e9).toInt

      if (i > 0) dp(i1(i-1))(i2(i-1)) = math.min(dp(i1(i-1))(i2(i-1)), dp(i1())(i2()) + D)
      dp(i1(i+1))(i2(i+1)) = math.min(dp(i1(i+1))(i2(i+1)), dp(i1())(i2()) + D)
      dp(i1(i*2))(i2(i*2)) = math.min(dp(i1(i*2))(i2(i*2)), dp(i1())(i2()) + A)
      dp(i1(i*3))(i2(i*3)) = math.min(dp(i1(i*3))(i2(i*3)), dp(i1())(i2()) + B)
      dp(i1(i*5))(i2(i*5)) = math.min(dp(i1(i*5))(i2(i*5)), dp(i1())(i2()) + C)
    }

    println(dp((N / 10e9).toInt)((N % 10e9).toInt))
  }
}
