# Original solution
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D






T = int(eval(input()))
for _ in range(T):
    N, A, B, C, D = list(map(int, input().split()))
    S = set()
    E = []
    Q = deque([N])
    while Q:
        x = deque.popleft(Q)
        if x in S: continue
        S.add(x)
        if x == 0: continue
        if x <= 10:
            nx = 0
            dd = D * x
            deque.append(Q, nx)
            E.append((x, nx, dd))
        if x % 2 == 0:
            nx = x // 2
            dd = min(A, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x > 1:
            nx = x // 2
            dd = min(A + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
            nx = x // 2 + 1
            dd = min(A + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        if x % 3 == 0:
            nx = x // 3
            dd = min(B, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x % 3 == 1:
            nx = x // 3
            dd = min(B + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        else:
            nx = x // 3 + 1
            dd = min(B + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        if x % 5 == 0:
            nx = x // 5
            dd = min(C, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x % 5 == 1:
            nx = x // 5
            dd = min(C + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 2:
            nx = x // 5
            dd = min(C + D * 2, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 3:
            nx = x // 5 + 1
            dd = min(C + D * 2, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 4:
            nx = x // 5 + 1
            dd = min(C + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
    
    # print("E =", len(E), E)
    A = []
    for a, b, d in E:
        A.append(a)
        A.append(b)
    A = sorted(list(set(A)))
    I = {a: i for i, a in enumerate(A)}
    E = [(I[a], I[b], d) for a, b, d in E]
    NN = len(A)
    # print("E =", len(E), E)
    EE = [[] for _ in range(NN)]
    for a, b, d in E:
        EE[a].append((b, d))
    print((dijkstra(NN, EE, I[N])[0]))
    
    # print("-----")

# Optimized solution
from functools import lru_cache

def calc(n):
    @lru_cache(maxsize=None)
    def rec(n):
        if n <= 0: return 0
        S = [2, 3, 5]
        mi = D * n
        for i, a in enumerate(S):
            for j in range(-a//2, a//2 + 1):
                if (n + j) % a == 0 and (n + j) // a < n:
                    mi = min(mi, rec((n+j) // a) + X[i] + D * abs(j))
        return mi
    return rec(n)

T = int(eval(input()))
for _ in range(T):
    N, A, B, C, D = list(map(int, input().split()))
    X = (A, B, C)
    print((calc(N)))