check=dict()

N,z,d=0,[],0

#ttfは235、chaはabc



def dfs_sub(n,ttf,cha):

    global check,d



    #-1ずつしていく場合

    check[0]=min(check[n]+n*d,check[0])



    #最寄りまで-してく場合

    x1,x2=n//ttf,n%ttf

    if x1 in check:

        if check[x1]>check[n]+x2*d+cha:

            check[x1]=check[n]+x2*d+cha

            dfs(x1)

    else:

        check[x1]=check[n]+x2*d+cha

        dfs(x1)



    #最寄りまで+1してく場合

    x1,x2=n//ttf+1,ttf-n%ttf

    if x1 in check:

        if check[x1]>check[n]+x2*d+cha:

            check[x1]=check[n]+x2*d+cha

            dfs(x1)

    else:

        check[x1]=check[n]+x2*d+cha

        dfs(x1)





def dfs(n):

    global z

    for i,j in z:

        dfs_sub(n,i,j)



t=int(eval(input()))

for i in range(t):

    N,*b,d=list(map(int,input().split()))

    z=list(zip([2,3,5],b))

    check={N:0,0:N*d}

    dfs(N)

    print((check[0]))

check=dict()

N,z,d=0,[],0

#ttfは235、chaはabc



def dfs_sub(n,ttf,cha):

    global check,d



    #-1ずつしていく場合

    check[0]=min(check[n]+n*d,check[0])



    #最寄りまで-してく場合

    x1,x2=n//ttf,n%ttf

    if x1 in check:

        if check[x1]>check[n]+x2*d+cha:

            check[x1]=check[n]+x2*d+cha

            dfs(x1)

    else:

        check[x1]=check[n]+x2*d+cha

        dfs(x1)



    #最寄りまで+1してく場合

    x1,x2=n//ttf+1,ttf-n%ttf

    if x1 in check:

        if check[x1]>check[n]+x2*d+cha:

            check[x1]=check[n]+x2*d+cha

            dfs(x1)

    else:

        check[x1]=check[n]+x2*d+cha

        dfs(x1)





def dfs(n):

    global b

    for i,j in zip([2,3,5],b):

        dfs_sub(n,i,j)



t=int(eval(input()))

for i in range(t):

    N,*b,d=list(map(int,input().split()))

    z=list(zip([2,3,5],b))

    check={N:0,0:N*d}

    dfs(N)

    print((check[0]))

check = dict()
N, z, d = 0, [], 0
# ttfは235、chaはabc
def dfs_sub(n, ttf, cha):
    global check, d
    # -1ずつしていく場合
    check[0] = min(check[n] + n * d, check[0])
    # 最寄りまで-してく場合
    x1, x2 = n // ttf, n % ttf
    if x1 in check:
        if check[x1] > check[n] + x2 * d + cha:
            check[x1] = check[n] + x2 * d + cha
            dfs(x1)
    else:
        check[x1] = check[n] + x2 * d + cha
        dfs(x1)
    # 最寄りまで+1してく場合
    x1, x2 = n // ttf + 1, ttf - n % ttf
    if x1 in check:
        if check[x1] > check[n] + x2 * d + cha:
            check[x1] = check[n] + x2 * d + cha
            dfs(x1)
    else:
        check[x1] = check[n] + x2 * d + cha
        dfs(x1)


def dfs(n):
    global z
    for i, j in z:
        dfs_sub(n, i, j)


t = int(eval(input()))
for i in range(t):
    N, *b, d = list(map(int, input().split()))
    z = list(zip([2, 3, 5], b))
    check = {N: 0, 0: N * d}
    dfs(N)
    print((check[0]))

check = dict()
N, z, d = 0, [], 0
# ttfは235、chaはabc
def dfs_sub(n, ttf, cha):
    global check, d
    # -1ずつしていく場合
    check[0] = min(check[n] + n * d, check[0])
    # 最寄りまで-してく場合
    x1, x2 = n // ttf, n % ttf
    if x1 in check:
        if check[x1] > check[n] + x2 * d + cha:
            check[x1] = check[n] + x2 * d + cha
            dfs(x1)
    else:
        check[x1] = check[n] + x2 * d + cha
        dfs(x1)
    # 最寄りまで+1してく場合
    x1, x2 = n // ttf + 1, ttf - n % ttf
    if x1 in check:
        if check[x1] > check[n] + x2 * d + cha:
            check[x1] = check[n] + x2 * d + cha
            dfs(x1)
    else:
        check[x1] = check[n] + x2 * d + cha
        dfs(x1)


def dfs(n):
    global b
    for i, j in zip([2, 3, 5], b):
        dfs_sub(n, i, j)


t = int(eval(input()))
for i in range(t):
    N, *b, d = list(map(int, input().split()))
    z = list(zip([2, 3, 5], b))
    check = {N: 0, 0: N * d}
    dfs(N)
    print((check[0]))

-    global z -    for i, j in z: +    global b +    for i, j in zip([2, 3, 5], b):