# https://atcoder.jp/contests/agc044/submissions/13542551



def main():

    from heapq import heappush, heappop



    T = int(eval(input()))

    for _ in range(T):

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



        h = [(0, N)]  # cost,value

        checked = set()



        ans = N * D + 1

        while h:

            cost, x = heappop(h)

            if cost >= ans: continue

            if x in checked: continue

            checked.add(x)



            # 0まで1ずつ減らす

            if ans > cost + x * D:

                ans = cost + x * D



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

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

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

                # nxの生成は不要

                nx, r = divmod(x, d)

                if nx not in checked:

                    heappush(h, (cost + r * D + c, nx))

                if (nx + 1) not in checked:

                    heappush(h, (cost + (d - r) * D + c, nx + 1))



        print(ans)





if __name__ == '__main__':

    main()

# https://atcoder.jp/contests/agc044/submissions/13542551



def main():

    from heapq import heappush, heappop



    T = int(eval(input()))

    for _ in range(T):

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



        h = [(0, N)]  # cost,value

        checked = set()



        ans = N * D + 1

        while h:

            cost, x = heappop(h)

            if cost >= ans: continue

            if x in checked: continue

            checked.add(x)



            # 0まで1ずつ減らす

            if ans > cost + x * D:

                ans = cost + x * D



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

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

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

                # nxの生成は不要

                nx, r = divmod(x, d)

                if nx not in checked:

                    heappush(h, (cost + r * D + c, nx))

                if (r > 0) and ((nx + 1) not in checked):

                    heappush(h, (cost + (d - r) * D + c, nx + 1))



        print(ans)





if __name__ == '__main__':

    main()

# https://atcoder.jp/contests/agc044/submissions/13542551
def main():
    from heapq import heappush, heappop

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


if __name__ == "__main__":
    main()

# https://atcoder.jp/contests/agc044/submissions/13542551
def main():
    from heapq import heappush, heappop

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


if __name__ == "__main__":
    main()

-                if (nx + 1) not in checked: +                if (r > 0) and ((nx + 1) not in checked):