CodeEff/ECCO huggingface dataset:
# Original solution
def dfs(x):
  m=x//2
  if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
    dp[m]=dp[x]+abs(2*m-x)*d+a
    dfs(m)
  m=0--x//2
  if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
    dp[m]=dp[x]+abs(2*m-x)*d+a
    dfs(m)
  m=x//3
  if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
    dp[m]=dp[x]+abs(3*m-x)*d+b
    dfs(m)
  m=0--x//3
  if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
    dp[m]=dp[x]+abs(3*m-x)*d+b
    dfs(m)
  m=x//5
  if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
    dp[m]=dp[x]+abs(5*m-x)*d+c
    dfs(m)
  m=0--x//5
  if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
    dp[m]=dp[x]+abs(5*m-x)*d+c
    dfs(m)
def solve():
  dp[n]=0
  dfs(n)
  return min(dp[i]+abs(i)*d for i in dp)
for _ in range(int(eval(input()))):
  n,a,b,c,d=list(map(int,input().split()))
  dp={}
  print((solve()))

# Optimized solution
import sys
input=sys.stdin.readline
def main():
  def dfs(x):
    m=x//2
    if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
      dp[m]=dp[x]+abs(2*m-x)*d+a
      dfs(m)
    m=0--x//2
    if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
      dp[m]=dp[x]+abs(2*m-x)*d+a
      dfs(m)
    m=x//3
    if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
      dp[m]=dp[x]+abs(3*m-x)*d+b
      dfs(m)
    m=0--x//3
    if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
      dp[m]=dp[x]+abs(3*m-x)*d+b
      dfs(m)
    m=x//5
    if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
      dp[m]=dp[x]+abs(5*m-x)*d+c
      dfs(m)
    m=0--x//5
    if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
      dp[m]=dp[x]+abs(5*m-x)*d+c
      dfs(m)
  def solve():
    dp[n]=0
    dfs(n)
    return min(dp[i]+abs(i)*d for i in dp)
  for _ in range(int(eval(input()))):
    n,a,b,c,d=list(map(int,input().split()))
    dp={}
    print((solve()))
if __name__ == "__main__":
  main()
# Original solution

#from collections import defaultdict
#from pprint import pprint
#from collections import deque
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
#import numpy as np
#import math
# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)/2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(eval(input()))

nabcd = [list(map(int,input().split())) for _ in range(t)]


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print((func(n)))
    #print(memo)


# Optimized solution

#from collections import defaultdict
#from pprint import pprint
#from collections import deque
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
#import numpy as np
#import math
# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)//2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(eval(input()))

nabcd = [list(map(int,input().split())) for _ in range(t)]


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print((func(n)))
    #print(memo)
# Original solution
DP = {}

def solve(n, a, b, c, d):
    if n <= 0: 
        return 0
    if n == 1:
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-4, 5):
        num = n + i
        trash = abs(i)*d
        if num < 0:
            continue
        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = list(map(int, input().split()))
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print((solve(n, a, b, c,d)))
    
t = int(eval(input()))
for _ in range(t):
    solve2()


# Optimized solution
DP = {}

def solve(n, a, b, c, d):
    if n <= 0: 
        return 0
    if n == 1:
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-3, 4):
        num = n + i
        trash = abs(i)*d
        if num < 0:
            continue
        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = list(map(int, input().split()))
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print((solve(n, a, b, c,d)))
    
t = int(eval(input()))
for _ in range(t):
    solve2()
# Original solution
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = [(3, B), (5, C), (2, A)]
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if cost >= ans:
            continue

        for r, co1 in abc:
            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            if a2 > r - a2:
                a1 += 1
                a2 = r - a2

            cd = a2 * D
            if (rest - a1) * D < co1 + cd:
                ans = min(ans, rest*D + cost)
            else:
                co2 = cost + co1
                heappush(dq, (co2 + cd, a1))

        if a2 == 1:
            heappush(dq, (cost+A+D, a1+1))


    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


# Optimized solution
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = [(2, A), (3, B), (5, C),]
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if cost >= ans:
            continue

        for r, co1 in abc:
            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            a3 = r - a2
            if a2 == a3:
                heappush(dq, (cost + co1 + a3*D, a1+1))
            elif a2 > a3:
                a1 += 1
                a2 = a3

            cd = a2 * D
            if (rest - a1) * D < co1 + cd:
                ans = min(ans, rest*D + cost)
            else:
                co2 = cost + co1
                heappush(dq, (co2 + cd, a1))

    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()
# Original solution
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = [(2, A), (3, B), (5, C),]
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if cost >= ans:
            continue

        for r, co1 in abc:
            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            a3 = r - a2
            if a2 == a3:
                heappush(dq, (cost + co1 + a3*D, a1+1))
            elif a2 > a3:
                a1 += 1
                a2 = a3

            cd = a2 * D
            if (rest - a1) * D < co1 + cd:
                ans = min(ans, rest*D + cost)
            else:
                co2 = cost + co1
                heappush(dq, (co2 + cd, a1))

    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


# Optimized solution
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = list(map(lambda x: (x[0], x[1], x[0]*x[1]/((x[0]-1)*D)) ,[(2, A), (3, B), (5, C),]))
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if cost >= ans:
            continue

        for r, co1, n2 in abc:
            if rest < n2:
                ans = min(ans, rest*D + cost)
                continue

            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            a3 = r - a2
            if a2 == a3:
                heappush(dq, (cost + co1 + a3*D, a1+1))
            elif a2 > a3:
                a1 += 1
                a2 = a3

            heappush(dq, (cost + co1 + a2*D, a1))

    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()
# Original solution
import sys
sys.setrecursionlimit(10**7)
def dfs(x):
    if x == 0:
        return 0
    if x == 1:
        return d
    if x in dic:
        return dic[x]
    l2 = x//2
    r2 = (x+1)//2
    l3 = x//3
    r3 = (x+2)//3
    l5 = x//5
    r5 = (x+4)//5
    count = min(x*d,10**18)
    count = min(count,abs(l2*2-x)*d+a+dfs(l2))
    count = min(count,abs(r2*2-x)*d+a+dfs(r2))
    count = min(count,abs(l3*3-x)*d+b+dfs(l3))
    count = min(count,abs(r3*3-x)*d+b+dfs(r3))
    count = min(count,abs(l5*5-x)*d+c+dfs(l5))
    count = min(count,abs(r5*5-x)*d+c+dfs(r5))
    dic[x] = count
    return count

t = int(eval(input()))
for _ in range(t):
    n,a,b,c,d = list(map(int,input().split()))
    dic = {}
    print((dfs(n)))

# Optimized solution
import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)

def solve(x,a,b,c,d):
    @lru_cache(None)
    def dfs(x):
        if x == 0:
            return 0
        if x == 1:
            return d
        l2 = x//2
        r2 = (x+1)//2
        l3 = x//3
        r3 = (x+2)//3
        l5 = x//5
        r5 = (x+4)//5
        count = x*d
        count = min(count,abs(l2*2-x)*d+a+dfs(l2))
        count = min(count,abs(r2*2-x)*d+a+dfs(r2))
        count = min(count,abs(l3*3-x)*d+b+dfs(l3))
        count = min(count,abs(r3*3-x)*d+b+dfs(r3))
        count = min(count,abs(l5*5-x)*d+c+dfs(l5))
        count = min(count,abs(r5*5-x)*d+c+dfs(r5))
        return count
    return dfs(x)
t = int(eval(input()))
for _ in range(t):
    n,a,b,c,d = list(map(int,input().split()))
    print((solve(n,a,b,c,d)))
# Original solution
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

T = int(eval(input()))
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = INF
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
                now * D
            )
        return ret

    print((search(N)))


# Optimized solution
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

T = int(eval(input()))
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = now * D
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
            )
        return ret

    print((search(N)))
# Original solution
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

T = int(eval(input()))
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = now * D
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
            )
        return ret

    print((search(N)))


# Optimized solution
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

T = int(eval(input()))
INF = 10**18

for _ in range(T):
    N, A, B, C, D = list(map(int, input().split()))
    DC = tuple(zip((2, 3, 5), (A, B, C)))

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = now * D
        for div, cost in DC:
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
            )
        return ret

    print((search(N)))
# Original solution
import sys
sys.setrecursionlimit(10**9)


def solve(n, a, b, c, d):

    return memo[0]


t = int(eval(input()))
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    memo = {}

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost

            if m > 0:
                dfs(m // 2, cost + (m % 2) * d + a)
                dfs(m // 3, cost + (m % 3) * d + b)
                dfs(m // 5, cost + (m % 5) * d + c)

                dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
                dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
                dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

                dfs(0, cost + m * d)

    dfs(n, 0)
    print((memo[0]))


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

t = int(eval(input()))
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    memo = {}

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost

            if m > 0:
                dfs(m // 2, cost + (m % 2) * d + a)
                dfs(m // 3, cost + (m % 3) * d + b)
                dfs(m // 5, cost + (m % 5) * d + c)

                dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
                dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
                dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

                dfs(0, cost + m * d)

    dfs(n, 0)
    print((memo[0]))
# Original solution
import sys
sys.setrecursionlimit(10**9)

t = int(eval(input()))
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    memo = {0: n * d}

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost
            memo[0] = min(memo[0], cost + m * d)

            if m > 0:
                dfs(m // 2, cost + (m % 2) * d + a)
                dfs(m // 3, cost + (m % 3) * d + b)
                dfs(m // 5, cost + (m % 5) * d + c)

                dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
                dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
                dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

    dfs(n, 0)
    print((memo[0]))


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

t = int(eval(input()))
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    memo = {0: 0, 1: d}

    def dfs(m):
        if m in memo:
            return memo[m]
        else:
            res1 = m * d

            res2 = (m % 2) * d + a + dfs(m // 2)
            res3 = (m % 3) * d + b + dfs(m // 3)
            res4 = (m % 5) * d + c + dfs(m // 5)

            res5 = ((2 - (m % 2)) % 2) * d + a + dfs(
                (m + (2 - (m % 2)) % 2) // 2)
            res6 = ((3 - (m % 3)) % 3) * d + b + dfs(
                (m + (3 - (m % 3)) % 3) // 3)
            res7 = ((5 - (m % 5)) % 5) * d + c + dfs(
                (m + (5 - (m % 5)) % 5) // 5)

            memo[m] = min(res1, res2, res3, res4, res5, res6, res7)
            return memo[m]

    ans = dfs(n)
    print(ans)
# Original solution
# https://atcoder.jp/contests/agc044/submissions/13542551

def main():
    from heapq import heappush, heappop

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

        h = [(0, N)]  # cost,value
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            # 0まで1ずつ減らす
            if ans > cost + x * D:
                ans = cost + x * D

            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (nx + 1) not in checked:
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
# https://atcoder.jp/contests/agc044/submissions/13542551

def main():
    from heapq import heappush, heappop

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

        h = [(0, N)]  # cost,value
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            # 0まで1ずつ減らす
            if ans > cost + x * D:
                ans = cost + x * D

            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (r > 0) and ((nx + 1) not in checked):
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()
# Original solution
# heapq -> deque

def main():
    from collections import defaultdict, deque

    inf = 10 ** 27

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

        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)

        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost >= checked[x]: continue
            checked[x] = cost

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                ncost = cost + r * D + c
                if checked[nx] > ncost:
                    dq.append((ncost, nx))
                ncost = cost + (d - r) * D + c
                if (r > 0) and (checked[nx + 1] > ncost):
                    dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
# heapq -> deque

def main():
    from collections import defaultdict, deque

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

        inf = N * D + 1

        dq = deque()
        dq.append((0, N))  # cost,value

        checked = defaultdict(lambda: inf)
        checked[N] = 0

        ans = inf
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost > checked[x]: continue

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                nx, r = divmod(x, d)
                ncost = cost + r * D + c
                if checked[nx] > ncost:
                    checked[nx] = ncost
                    dq.append((ncost, nx))

                if r == 0: continue
                ncost = cost + (d - r) * D + c
                if checked[nx + 1] > ncost:
                    checked[nx + 1] = ncost
                    dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()