t = int(eval(input()))



import sys

sys.setrecursionlimit(10 ** 6)



def calc(x):

    if x in dp:

        return dp[x]

    

    divs = [5, 3, 2]

    costs = [c, b, a]

    res = d * x

    for div, cost in zip(divs, costs):

        dived = x//div

        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)

        if x > div:

            dived = x//div+1

            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)

    dp[x] = res

    return res



for _ in range(t):

    n, a, b, c, d = list(map(int, input().split()))

    dp = {}

    dp[0] = 0

    dp[1] = d

    print((calc(n)))

t = int(eval(input()))



def calc(x):

    if x not in dp:

        divs = [5, 3, 2]

        costs = [c, b, a]

        values = lambda div, cost: [calc(x // div) + cost + x % div * d, calc((x + div - 1) // div) + cost + (-x) % div * d]

        dp[x] = min(x * d, *[value for div, cost in zip(divs, costs) for value in values(div, cost)])

    return dp[x]



for _ in range(t):

    n, a, b, c, d = list(map(int, input().split()))

    dp = {0: 0, 1: d}

    print((calc(n)))

t = int(eval(input()))
import sys

sys.setrecursionlimit(10**6)


def calc(x):
    if x in dp:
        return dp[x]
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x
    for div, cost in zip(divs, costs):
        dived = x // div
        res = min(res, calc(dived) + cost + abs(x - dived * div) * d)
        if x > div:
            dived = x // div + 1
            res = min(res, calc(dived) + cost + abs(x - dived * div) * d)
    dp[x] = res
    return res


for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {}
    dp[0] = 0
    dp[1] = d
    print((calc(n)))

t = int(eval(input()))


def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [
            calc(x // div) + cost + x % div * d,
            calc((x + div - 1) // div) + cost + (-x) % div * d,
        ]
        dp[x] = min(
            x * d,
            *[value for div, cost in zip(divs, costs) for value in values(div, cost)]
        )
    return dp[x]


for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {0: 0, 1: d}
    print((calc(n)))

-import sys - -sys.setrecursionlimit(10**6) -    if x in dp: -        return dp[x] -    divs = [5, 3, 2] -    costs = [c, b, a] -    res = d * x -    for div, cost in zip(divs, costs): -        dived = x // div -        res = min(res, calc(dived) + cost + abs(x - dived * div) * d) -        if x > div: -            dived = x // div + 1 -            res = min(res, calc(dived) + cost + abs(x - dived * div) * d) -    dp[x] = res -    return res +    if x not in dp: +        divs = [5, 3, 2] +        costs = [c, b, a] +        values = lambda div, cost: [ +            calc(x // div) + cost + x % div * d, +            calc((x + div - 1) // div) + cost + (-x) % div * d, +        ] +        dp[x] = min( +            x * d, +            *[value for div, cost in zip(divs, costs) for value in values(div, cost)] +        ) +    return dp[x] -    dp = {} -    dp[0] = 0 -    dp[1] = d +    dp = {0: 0, 1: d}