# heapq -> deque



def main():

    from collections import defaultdict, deque



    inf = 10 ** 27



    T = int(eval(input()))

    for _ in range(T):

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



        dq = deque()

        dq.append((0, N))  # cost,value

        checked = defaultdict(lambda: inf)



        ans = N * D + 1

        while dq:

            cost, x = dq.popleft()

            if cost >= ans: continue

            if cost >= checked[x]: continue

            checked[x] = cost



            # 0まで1ずつ減らす

            ans = min(ans, cost + x * D)



            for d, c in ((2, A), (3, B), (5, C)):

                # すでにheapqからnxがpopしていれば

                # より低コストでnxを生成できているので

                # nxの生成は不要

                nx, r = divmod(x, d)

                ncost = cost + r * D + c

                if checked[nx] > ncost:

                    dq.append((ncost, nx))

                ncost = cost + (d - r) * D + c

                if (r > 0) and (checked[nx + 1] > ncost):

                    dq.append((ncost, nx + 1))



        print(ans)





if __name__ == '__main__':

    main()

# heapq -> deque



def main():

    from collections import defaultdict, deque



    T = int(eval(input()))

    for _ in range(T):

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



        inf = N * D + 1



        dq = deque()

        dq.append((0, N))  # cost,value



        checked = defaultdict(lambda: inf)

        checked[N] = 0



        ans = inf

        while dq:

            cost, x = dq.popleft()

            if cost >= ans: continue

            if cost > checked[x]: continue



            # 0まで1ずつ減らす

            ans = min(ans, cost + x * D)



            for d, c in ((2, A), (3, B), (5, C)):

                nx, r = divmod(x, d)

                ncost = cost + r * D + c

                if checked[nx] > ncost:

                    checked[nx] = ncost

                    dq.append((ncost, nx))



                if r == 0: continue

                ncost = cost + (d - r) * D + c

                if checked[nx + 1] > ncost:

                    checked[nx + 1] = ncost

                    dq.append((ncost, nx + 1))



        print(ans)





if __name__ == '__main__':

    main()

# heapq -> deque
def main():
    from collections import defaultdict, deque

    inf = 10**27
    T = int(eval(input()))
    for _ in range(T):
        N, A, B, C, D = list(map(int, input().split()))
        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)
        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans:
                continue
            if cost >= checked[x]:
                continue
            checked[x] = cost
            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)
            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                ncost = cost + r * D + c
                if checked[nx] > ncost:
                    dq.append((ncost, nx))
                ncost = cost + (d - r) * D + c
                if (r > 0) and (checked[nx + 1] > ncost):
                    dq.append((ncost, nx + 1))
        print(ans)


if __name__ == "__main__":
    main()

# heapq -> deque
def main():
    from collections import defaultdict, deque

    T = int(eval(input()))
    for _ in range(T):
        N, A, B, C, D = list(map(int, input().split()))
        inf = N * D + 1
        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)
        checked[N] = 0
        ans = inf
        while dq:
            cost, x = dq.popleft()
            if cost >= ans:
                continue
            if cost > checked[x]:
                continue
            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)
            for d, c in ((2, A), (3, B), (5, C)):
                nx, r = divmod(x, d)
                ncost = cost + r * D + c
                if checked[nx] > ncost:
                    checked[nx] = ncost
                    dq.append((ncost, nx))
                if r == 0:
                    continue
                ncost = cost + (d - r) * D + c
                if checked[nx + 1] > ncost:
                    checked[nx + 1] = ncost
                    dq.append((ncost, nx + 1))
        print(ans)


if __name__ == "__main__":
    main()

-    inf = 10**27 +        inf = N * D + 1 -        ans = N * D + 1 +        checked[N] = 0 +        ans = inf -            if cost >= checked[x]: +            if cost > checked[x]: -            checked[x] = cost -                # すでにheapqからnxがpopしていれば -                # より低コストでnxを生成できているので -                # nxの生成は不要 +                    checked[nx] = ncost +                if r == 0: +                    continue -                if (r > 0) and (checked[nx + 1] > ncost): +                if checked[nx + 1] > ncost: +                    checked[nx + 1] = ncost