You start with the number 0 and you want to reach the number N.  You can change the number, paying a certain amount of coins, with the following operations:    * Multiply the number by 2, paying A coins.   * Multiply the number by 3, paying B coins.   * Multiply the number by 5, paying C coins.   * Increase or decrease the number by 1, paying D coins.  You can perform these operations in arbitrary order and an arbitrary number of times.  What is the minimum number of coins you need to reach N?  **You have to solve T testcases.**
t = int(input())
n, a, b, c, d = list(), list(), list(), list(), list()
for i in range(t):
    x = list(map(int, input().split()))
    n.append(x[0])
    a.append(x[1])
    b.append(x[2])
    c.append(x[3])
    d.append(x[4])

for i in range(t):
    print(a[i] * n[i])
    

#import sys


times = int(input())
x = []
for t in range(times):
    x.append(list(map(int, input().split())))


def f(n):
    if n == 0:
        return 0
    if n == 1:
        return d
    if n in dic:
        return dic[n]

    if n%2 == 0:
        n2 = f(n // 2) + a
    elif n%2 == 1:
        n2 = min(f((n-1) // 2) + d, f((n+1) // 2) + d) + a

    if n%3 == 0:
        n3 = f(n // 3) + b
    elif n%3 == 1:
        n3 = min(f((n-1) // 3) + d, f((n+2) // 3) + 2*d) + b
    elif n%3 == 2:
        n3 = min(f((n-2) // 3) + 2*d, f((n+1) // 3) + d) + b

    if n%5 == 0:
        n5 = f(n // 5) + c
    elif n%5 == 1:
        n5 = min(f((n-1) // 5) + d, f((n+4) // 5) + 4*d) + c
    elif n%5 == 2:
        n5 = min(f((n-2) // 5) + 2*d, f((n+3) // 5) + 3*d) + c
    elif n%5 == 3:
        n5 = min(f((n-3) // 5) + 3*d, f((n+2) // 5) + 2*d) + c
    elif n%5 == 4:
        n5 = min(f((n-4) // 5) + 4*d, f((n+1) // 5) + d) + c

    Y = min(n2, n3, n5, n*d)
    dic[n] = Y
    return Y


for t in range(times):
    n, a, b, c, d = x[t][0], x[t][1], x[t][2], x[t][3], x[t][4]
    dic = {}
    print(f(n))

