# Original solution
import sys

sys.setrecursionlimit(10**6)

# def dfs(t,ans):
#     global a,b,c,d fin
#     if t % 5 == 0:
#         if c > 4*t//5 * d:
#             fin = min(fin,ans+4*t//5*d)
#         else:
#             dfs(t//5,ans+c)
#     if t % 3 == 0:
#         if b > 2*t//3 * d:
#             fin = min(fin,ans+2*t//3*d)
#         else:
#             dfs(t//3,ans+b)
#     if t % 2 == 0:
#         if a > t//2 * d:
#             fin = min(fin,ans+t//2*d)
#         else:
#             dfs(t//2,ans+a)
def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    # print(t)
    dic1[t] = ans
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        if t % 5 == 0:
            if c > 4*t//5 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//5 not in dic1:
                    solve(t//5,ans+c)
                elif dic1[t//5] > ans+c:
                    solve(t//5,ans+c)
        if t % 3 == 0:
            if b > 2*t//3 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//3 not in dic1:
                    solve(t//3,ans+b)
                elif dic1[t//3] > ans+b:
                    solve(t//3,ans+b)

        if t % 2 == 0:
            if a > t//2 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//2 not in dic1:
                    solve(t//2,ans+a)
                elif dic1[t//2] > ans+a:
                    solve(t//2,ans+a)
  
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
            if u % 3 == 0:
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)

            if u % 2 == 0:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
        # while fa or fb or fc:
        #     u = t+cnt
        #     ans_temp = ans + d*abs(i)
        #     if u % 5 == 0:
        #         if c > 4*u//5 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//5,ans_temp+c)
        #     if u % 3 == 0:
        #         if b > 2*u//3 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//3,ans_temp+b)
        #     if u % 2 == 0:
        #         if a > u//2 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//2,ans_temp+a)
            # if u == 1:
            #     fin = min(fin,ans_temp+d)
t = int(eval(input()))
al = [1,-1,2,-2]


for i in range(t):
    n,a,b,c,d = list(map(int,input().split()))
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

# Optimized solution
import sys
sys.setrecursionlimit(10**6)

def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
            if u % 3 == 0:
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b

            if u % 2 == 0:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a

t = int(eval(input()))
al = [0,-1,1,-2,2]

for i in range(t):
    n,a,b,c,d = list(map(int,input().split()))
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)