T = int(eval(input()))



while(T > 0):

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

    dp = {}



    def d(n):

        if n == 0:

            return 0

        if n == 1:

            return D



        if n in dp:

            return dp[n]



        ret = min(

            D * n,

            D * abs(n - (n // 2) * 2) + A + d(n // 2),

            D * abs(n - ((n+1) // 2) * 2) + A + d((n+1) // 2),

            D * abs(n - (n // 3) * 3) + B + d(n // 3),

            D * abs(n - ((n + 2) // 3) * 3) + B + d((n + 2) // 3),

            D * abs(n - (n // 5) * 5) + C + d(n // 5),

            D * abs(n - ((n + 4) // 5) * 5) + C + d((n + 4) // 5),

        )



        dp[n] = ret

        return ret



    print((d(N)))

    T -= 1
T = int(eval(input()))



while(T > 0):

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

    memo = {}

    def d(n):

        if n == 0:

            return 0



        if n == 1:

            return D



        if n in memo:

            return memo[n]



        ret = n * D



        if (n % 2 == 0):

            ret = min(ret, A + d(n // 2))

        else:

            ret = min(ret, (n%2)*D + A + d(n // 2), (2-n%2)*D + A + d((n+(2-n%2))//2))



        if (n % 3 == 0):

            ret = min(ret, B + d(n // 3))

        else:

            ret = min(ret, (n%3)*D + B + d(n // 3), (3-n%3)*D + B + d((n+(3-n%3))//3))



        if (n % 5 == 0):

            ret = min(ret, C + d(n // 5))

        else:

            ret = min(ret, (n%5)*D + C + d(n // 5), (5-n%5)*D + C + d((n+(5-n%5))//5))



        memo[n] = ret

        return ret



    print((d(N)))

    T -= 1





T = int(eval(input()))
while T > 0:
    N, A, B, C, D = list(map(int, input().split()))
    dp = {}

    def d(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in dp:
            return dp[n]
        ret = min(
            D * n,
            D * abs(n - (n // 2) * 2) + A + d(n // 2),
            D * abs(n - ((n + 1) // 2) * 2) + A + d((n + 1) // 2),
            D * abs(n - (n // 3) * 3) + B + d(n // 3),
            D * abs(n - ((n + 2) // 3) * 3) + B + d((n + 2) // 3),
            D * abs(n - (n // 5) * 5) + C + d(n // 5),
            D * abs(n - ((n + 4) // 5) * 5) + C + d((n + 4) // 5),
        )
        dp[n] = ret
        return ret

    print((d(N)))
    T -= 1

T = int(eval(input()))
while T > 0:
    N, A, B, C, D = list(map(int, input().split()))
    memo = {}

    def d(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo:
            return memo[n]
        ret = n * D
        if n % 2 == 0:
            ret = min(ret, A + d(n // 2))
        else:
            ret = min(
                ret,
                (n % 2) * D + A + d(n // 2),
                (2 - n % 2) * D + A + d((n + (2 - n % 2)) // 2),
            )
        if n % 3 == 0:
            ret = min(ret, B + d(n // 3))
        else:
            ret = min(
                ret,
                (n % 3) * D + B + d(n // 3),
                (3 - n % 3) * D + B + d((n + (3 - n % 3)) // 3),
            )
        if n % 5 == 0:
            ret = min(ret, C + d(n // 5))
        else:
            ret = min(
                ret,
                (n % 5) * D + C + d(n // 5),
                (5 - n % 5) * D + C + d((n + (5 - n % 5)) // 5),
            )
        memo[n] = ret
        return ret

    print((d(N)))
    T -= 1

-    dp = {} +    memo = {} -        if n in dp: -            return dp[n] -        ret = min( -            D * n, -            D * abs(n - (n // 2) * 2) + A + d(n // 2), -            D * abs(n - ((n + 1) // 2) * 2) + A + d((n + 1) // 2), -            D * abs(n - (n // 3) * 3) + B + d(n // 3), -            D * abs(n - ((n + 2) // 3) * 3) + B + d((n + 2) // 3), -            D * abs(n - (n // 5) * 5) + C + d(n // 5), -            D * abs(n - ((n + 4) // 5) * 5) + C + d((n + 4) // 5), -        ) -        dp[n] = ret +        if n in memo: +            return memo[n] +        ret = n * D +        if n % 2 == 0: +            ret = min(ret, A + d(n // 2)) +        else: +            ret = min( +                ret, +                (n % 2) * D + A + d(n // 2), +                (2 - n % 2) * D + A + d((n + (2 - n % 2)) // 2), +            ) +        if n % 3 == 0: +            ret = min(ret, B + d(n // 3)) +        else: +            ret = min( +                ret, +                (n % 3) * D + B + d(n // 3), +                (3 - n % 3) * D + B + d((n + (3 - n % 3)) // 3), +            ) +        if n % 5 == 0: +            ret = min(ret, C + d(n // 5)) +        else: +            ret = min( +                ret, +                (n % 5) * D + C + d(n // 5), +                (5 - n % 5) * D + C + d((n + (5 - n % 5)) // 5), +            ) +        memo[n] = ret