#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import deque
from collections import defaultdict
import heapq
INF = float("inf")


def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        d = defaultdict(lambda: INF)
        stack = [(0, N)]
        d[N] = 0
        while len(stack) > 0:
            c, n = heapq.heappop(stack)
            if c > d[1]:
                break
            # print(c, n)
            cost = [A, B, C]
            for i, p in enumerate((2, 3, 5)):
                # A,B,Cのアクションを行う場合
                if n % p == 0 and d[n//p] > c+cost[i]:
                    d[n//p] = c+cost[i]
                    heapq.heappush(stack, (c+cost[i], n//p))

                # Dの扱い
                # A,B,Cのアクションの代わりとして行う場合
                if cost[i] > (n-n//p)*D and d[n//p] > c+(n-n//p)*D:
                    d[n//p] = c+(n-n//p)*D
                    heapq.heappush(stack, (c+(n-n//p)*D, n//p))

                # Dの扱い
                # A、B,Cのアクションと連携して行う場合
                if n % p != 0:
                    m = n % p
                    # m回Dを行って、pを行う
                    if d[(n-m)//p] > c+cost[i]+m*D:
                        d[(n-m)//p] = c+cost[i]+m*D
                        heapq.heappush(stack, (c+cost[i]+m*D, (n-m)//p))
                    # p-m回Dを行って、pを行う
                    m = p - m
                    if d[(n+m)//p] > c+cost[i]+m*D:
                        d[(n+m)//p] = c+cost[i]+m*D
                        heapq.heappush(stack, (c+cost[i]+m*D, (n+m)//p))

            #         # if n % 2 == 0:
            #         #     if A > (n//2)*D:
            #         #         if d[n//2] > c+(n//2)*D:
            #         #             d[n//2] = c+(n//2)*D
            #         #             heapq.heappush(stack, (c+(n//2)*D, n//2))
            #         #     else:
            #         #         if d[n//2] > c+A:
            #         #             d[n//2] = c+A
            #         #             heapq.heappush(stack, (c+A, n//2))
            #         # if n % 3 == 0:
            #         #     if B > (n-n//3)*D:
            #         #         if d[n//3] > c+(n-n//3)*D:
            #         #             d[n//3] = c+(n-n//3)*D
            #         #             heapq.heappush(stack, (c+(n-n//3)*D, n//3))
            #         #     else:
            #         #         if d[n//3] > c+B:
            #         #             d[n//3] = c+B
            #         #             heapq.heappush(stack, (c+B, n//3))
            #         # if n % 5 == 0:
            #         #     if C > (n-n//5)*D:
            #         #         if d[n//5] > c+(n-n//5)*D:
            #         #             d[n//5] = c+(n-n//5)*D
            #         #             heapq.heappush(stack, (c+(n-n//5)*D, n//5))
            #         #     if d[n//5] > c+C:
            #         #         d[n//5] = c+C
            #         #         heapq.heappush(stack, (c+C, n//5))
            # if n % 2 == 1:
            #     if d[(n-1)//2] > c+A+D:
            #         d[(n-1)//2] = c+A+D
            #         heapq.heappush(stack, (c+A+D, (n-1)//2))
            #     if d[(n+1)//2] > c+D+A:
            #         d[(n+1)//2] = c+D+A
            #         heapq.heappush(stack, (c+D+A, (n+1)//2))
            # if n % 3 != 0:
            #     m = n % 3
            #     if d[(n-m)//3] > c+B+m*D:
            #         d[(n-m)//3] = c+B+m*D
            #         heapq.heappush(stack, (c+B+m*D, (n-m)//3))
            #     if d[(n-m+3)//3] > c+B+(3-m)*D:
            #         d[(n-m+3)//3] = c+B+(3-m)*D
            #         heapq.heappush(stack, (c+B+(3-m)*D, (n-m+3)//3))
            # if n % 5 != 0:
            #     m = n % 5
            #     if d[(n-m)//5] > c+C+m*D:
            #         d[(n-m)//5] = c+C+m*D
            #         heapq.heappush(stack, (c+C+m*D, (n-m)//5))
            #     if d[(n-m+5)//5] > c+C+(5-m)*D:
            #         d[(n-m+5)//5] = c+C+(5-m)*D
            #         heapq.heappush(stack, (c+C+(5-m)*D, (n-m+5)//5))

        print(d[1]+D)
        # return

        # 一番効率の良いアプローチで攻める貪欲ではどうか→組み合わせ次第
        # 作戦
        # Nが小さければDPができる。→あるiに到達するために必要なコインの最小数
        # 10**3程度までは貪欲で近づいて良さそうなイメージがある。そこから貪欲とする
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 75880