let t = stdin.ReadLine() |> int

let nabcds =
    [
        for _ in 0 .. t - 1 do
            let l = stdin.ReadLine().Split(' ') |> Array.map int64
            yield (l.[0], int l.[1], int l.[2], int l.[3], int l.[4])
    ]

let parent i = (i - 1) / 2
let left i = 2 * i + 1
let right i = 2 * i + 2

let ans: int list =
    [
        for i in 0 .. t - 1 do
            let heap = ResizeArray<int * int64>()

            let upHeap x =
                let size = heap.Count
                if size = 0 then
                    heap.Add(x)
                else
                    let mutable tmp = size
                    while tmp > 0 do
                        if fst heap.[parent tmp] > fst x then
                            heap.Insert(tmp, heap.[parent tmp])
                            tmp <- parent tmp
                        else
                            heap.Insert(tmp, x)
                            tmp <- 0

            let n, a, b, c, d = nabcds.[i]

            [a; b; c; d]
            |> List.iteri (
                fun i x ->
                    match i with
                    | 0 -> upHeap (a, 0L)
                    | 1 -> upHeap (b, 0L)
                    | 2 -> upHeap (c, 0L)
                    | _ -> upHeap (d, 1L))

            let downHeap =
                let size = heap.Count
                // heap.Remove(heap.[0]) |> ignore
                heap.Insert(0, heap.[size - 1])
                // heap.Remove(heap.[size - 1]) |> ignore
                heap.RemoveAt(size - 1)

                let mutable tmp = 0
                let mutable ok = false
                while not ok do
                    let l = left tmp
                    let r = right tmp
                    if r < size then
                        let k =
                            if fst heap.[l] < fst heap.[r] then
                                l
                            else
                                r
                        if heap.[k] < heap.[tmp] then
                            heap.Insert(k, heap.[tmp])
                            tmp <- k
                        else
                            ok <- true
                    elif l < size then
                        if heap.[l] < heap.[tmp] then
                            heap.Insert(l, heap.[tmp])
                            tmp <- l
                        else
                            ok <- true
                    else
                        ok <- true

            let mutable found = false
            while not found do
                let coins, m = heap.[0]
                if m = n then
                    found <- true
                    yield fst heap.[0]
                else
                    downHeap
                    [a; b; c; d]
                    |> List.iteri (
                        fun i x ->
                            match i with
                            | 0 -> upHeap (coins + a, 2L * m)
                            | 1 -> upHeap (coins + b, 3L * m)
                            | 2 -> upHeap (coins + c, 5L * m)
                            | _ ->
                                upHeap (coins + d, m + 1L)
                                if m > 0L then
                                    upHeap (coins + d, m - 1L))
    ]

ans
|> List.iter stdout.WriteLine
