import math

from functools import lru_cache



T = int(eval(input()))





class Resolver:

    def __init__(self, a, b, c, d):

        self.a = a

        self.b = b

        self.c = c

        self.d = d



    @lru_cache(maxsize=None)

    def resolve(self, n):

        if n == 0:

            return 0

        elif n == 1:

            return self.d

        else:

            div5f = n // 5

            div5c = (n + 4) // 5

            div3f = n // 3

            div3c = (n + 2) // 3

            div2f = n // 2

            div2c = (n + 1) // 2

            return min(

                self.d * n,

                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),

                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),

                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),

                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),

                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),

                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),

            )





for _ in range(T):

    N, A, B, C, D = list(map(int, input().split(' ')))

    resolver = Resolver(A, B, C, D)

    print((resolver.resolve(N)))

from functools import lru_cache



T = int(eval(input()))





def resolver(a, b, c, d):

    @lru_cache(maxsize=None)

    def _resolver(n):

        if n == 0:

            return 0

        elif n == 1:

            return d

        else:

            div5f = n // 5

            div5c = (n + 4) // 5

            div3f = n // 3

            div3c = (n + 2) // 3

            div2f = n // 2

            div2c = (n + 1) // 2

            return min(

                d * n,

                d * abs(n - div5f * 5) + c + _resolver(div5f),

                d * abs(n - div5c * 5) + c + _resolver(div5c),

                d * abs(n - div3f * 3) + b + _resolver(div3f),

                d * abs(n - div3c * 3) + b + _resolver(div3c),

                d * abs(n - div2f * 2) + a + _resolver(div2f),

                d * abs(n - div2c * 2) + a + _resolver(div2c),

            )



    return _resolver





for _ in range(T):

    N, A, B, C, D = list(map(int, input().split(' ')))

    print((resolver(A, B, C, D)(N)))

import math
from functools import lru_cache

T = int(eval(input()))


class Resolver:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    @lru_cache(maxsize=None)
    def resolve(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return self.d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                self.d * n,
                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),
                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),
                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),
                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),
                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),
                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),
            )


for _ in range(T):
    N, A, B, C, D = list(map(int, input().split(" ")))
    resolver = Resolver(A, B, C, D)
    print((resolver.resolve(N)))

from functools import lru_cache

T = int(eval(input()))


def resolver(a, b, c, d):
    @lru_cache(maxsize=None)
    def _resolver(n):
        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                d * n,
                d * abs(n - div5f * 5) + c + _resolver(div5f),
                d * abs(n - div5c * 5) + c + _resolver(div5c),
                d * abs(n - div3f * 3) + b + _resolver(div3f),
                d * abs(n - div3c * 3) + b + _resolver(div3c),
                d * abs(n - div2f * 2) + a + _resolver(div2f),
                d * abs(n - div2c * 2) + a + _resolver(div2c),
            )

    return _resolver


for _ in range(T):
    N, A, B, C, D = list(map(int, input().split(" ")))
    print((resolver(A, B, C, D)(N)))

-import math -class Resolver: -    def __init__(self, a, b, c, d): -        self.a = a -        self.b = b -        self.c = c -        self.d = d - +def resolver(a, b, c, d): -    def resolve(self, n): +    def _resolver(n): -            return self.d +            return d -                self.d * n, -                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f), -                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c), -                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f), -                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c), -                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f), -                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c), +                d * n, +                d * abs(n - div5f * 5) + c + _resolver(div5f), +                d * abs(n - div5c * 5) + c + _resolver(div5c), +                d * abs(n - div3f * 3) + b + _resolver(div3f), +                d * abs(n - div3c * 3) + b + _resolver(div3c), +                d * abs(n - div2f * 2) + a + _resolver(div2f), +                d * abs(n - div2c * 2) + a + _resolver(div2c), + +    return _resolver -    resolver = Resolver(A, B, C, D) -    print((resolver.resolve(N))) +    print((resolver(A, B, C, D)(N)))