import sys



divs = [2, 3, 5]



t = int(eval(input()))



for _ in range(t):

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

    costs = [a, b, c]



    dp = {}



    def dfs(x):

        if x in dp:

            return dp[x]



        # print(x, file=sys.stderr)



        if x == 0:

            dp[x] = 0

            return dp[x]



        ret = x * d

        for i in range(-4, 5):

            if x - i < 0:

                continue



            nx = x - i

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

                if nx % div != 0 or nx // div >= x:

                    continue



                ret = min(ret, dfs(nx // div) + cost + abs(i) * d)



        dp[x] = ret

        return ret



    print((dfs(n)))

divs = [2, 3, 5]



t = int(eval(input()))



for _ in range(t):

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

    costs = [a, b, c]



    dp = {0: 0}



    def dfs(x):

        if x in dp:

            return dp[x]



        ret = x * d



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

            lx = x // div * div

            ret = min(ret, dfs(lx // div) + cost + (x - lx) * d)



            if lx == x:

                continue

            lx += div

            if lx // div >= x:

                continue

            ret = min(ret, dfs(lx // div) + cost + (lx - x) * d)



        dp[x] = ret

        return ret



    print((dfs(n)))

import sys

divs = [2, 3, 5]
t = int(eval(input()))
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]
    dp = {}

    def dfs(x):
        if x in dp:
            return dp[x]
        # print(x, file=sys.stderr)
        if x == 0:
            dp[x] = 0
            return dp[x]
        ret = x * d
        for i in range(-4, 5):
            if x - i < 0:
                continue
            nx = x - i
            for cost, div in zip(costs, divs):
                if nx % div != 0 or nx // div >= x:
                    continue
                ret = min(ret, dfs(nx // div) + cost + abs(i) * d)
        dp[x] = ret
        return ret

    print((dfs(n)))

divs = [2, 3, 5]
t = int(eval(input()))
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]
    dp = {0: 0}

    def dfs(x):
        if x in dp:
            return dp[x]
        ret = x * d
        for cost, div in zip(costs, divs):
            lx = x // div * div
            ret = min(ret, dfs(lx // div) + cost + (x - lx) * d)
            if lx == x:
                continue
            lx += div
            if lx // div >= x:
                continue
            ret = min(ret, dfs(lx // div) + cost + (lx - x) * d)
        dp[x] = ret
        return ret

    print((dfs(n)))

-import sys - -    dp = {} +    dp = {0: 0} -        # print(x, file=sys.stderr) -        if x == 0: -            dp[x] = 0 -            return dp[x] -        for i in range(-4, 5): -            if x - i < 0: +        for cost, div in zip(costs, divs): +            lx = x // div * div +            ret = min(ret, dfs(lx // div) + cost + (x - lx) * d) +            if lx == x: -            nx = x - i -            for cost, div in zip(costs, divs): -                if nx % div != 0 or nx // div >= x: -                    continue -                ret = min(ret, dfs(nx // div) + cost + abs(i) * d) +            lx += div +            if lx // div >= x: +                continue +            ret = min(ret, dfs(lx // div) + cost + (lx - x) * d)