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())

testcase = [list(map(int,input().split())) for i in range(T)]

from math import ceil
from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,a,b,c,d):
    if n == 0:
        return 0
    if n == 1:
        return d
    else:
        return min((n-5*(n//5)) * d + c + f(n//5,a,b,c,d),(n-3*(n//3)) * d + b + f(n//3,a,b,c,d),(n-2*(n//2)) * d + a + f(n//2,a,b,c,d),
                   (5*ceil(n/5)-n) * d + c + f(ceil(n/5),a,b,c,d),(3*ceil(n/3)-n) * d + b + f(ceil(n/3),a,b,c,d),(2*ceil(n/2)-n) * d + a + f(ceil(n/2),a,b,c,d),n*d)

for n,a,b,c,d in testcase:
    print(f(n,a,b,c,d))
T = int(input())

testcase = [list(map(int,input().split())) for i in range(T)]

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,a,b,c,d):
    if n == 0:
        return 0
    if n == 1:
        return d
    else:
        return min((n-5*(n//5)) * d + c + f(n//5,a,b,c,d),(n-3*(n//3)) * d + b + f(n//3,a,b,c,d),(n-2*(n//2)) * d + a + f(n//2,a,b,c,d),
                   (5*((n+4)//5)-n) * d + c + f((n+4)//5,a,b,c,d),(3*((n+2)//3)-n) * d + b + f((n+2)//3,a,b,c,d),(2*((n+1)//2)-n) * d + a + f((n+1)//2,a,b,c,d),n*d)

for n,a,b,c,d in testcase:
    print(f(n,a,b,c,d))