Problem:
 Score : 400 points    Problem Statement 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.      Constraints  1 \le T \le 10  1 \le N \le 10^{18}  1 \le A, B, C, D \le 10^9  All numbers N, A, B, C, D are integers.         Input The input is given from Standard Input. The first line of the input is  T   Then, T lines follow describing the T testcases.
Each of the T lines has the format  N  A  B  C  D       Output For each testcase, print the answer on Standard Output followed by a newline.        Sample Input 1 5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321      Sample Output 1 20
19
26
3821859835
23441258666  For the first testcase, a sequence of moves that achieves the minimum cost of 20 is:   Initially x = 0 .  Pay 8 to increase by 1 ( x = 1 ).  Pay 1 to multiply by 2 ( x = 2 ).  Pay 1 to multiply by 2 ( x = 4 ).  Pay 2 to multiply by 3 ( x = 12 ).  Pay 8 to decrease by 1 ( x = 11 ).   For the second testcase, a sequence of moves that achieves the minimum cost of 19 is:   Initially x = 0 .  Pay 8 to increase by 1 ( x = 1 ).  Pay 1 to multiply by 2 ( x = 2 ).  Pay 2 to multiply by 5 ( x = 10 ).  Pay 8 to increase by 1 ( x = 11 ).

Solution (Python):
T=int(input())
ABCD=[list(map(int,input().split())) for i in range(T)]
from collections import deque
for N,a,b,c,d in ABCD:
    dic={N:0}
    q=deque([N])
    while q:
        n=q.popleft()
        x=dic[n]
        if n%2:
            if (n-1)//2 not in dic or min(x+a+d,x+(n-(n-1)//2)*d)<dic[(n-1)//2]:
                dic[(n-1)//2]=min(x+a+d,x+(n-(n-1)//2)*d)
                q.append((n-1)//2)
            if (n+1)//2 not in dic or x+a+d<dic[(n+1)//2]:
                dic[(n+1)//2]=x+a+d
                q.append((n+1)//2)
            if n-1==0:
                dic[0]=min(dic[0],x+d)
        else:
            if n//2 not in dic or x+a<dic[n//2]:
                dic[n//2]=x+a
                q.append(n//2)
        if n%3:
            y=n-n//3*3
            if (n-y)//3 not in dic or min(x+b+d*y,x+(n-(n-y)//3)*d)<dic[(n-y)//3]:
                dic[(n-y)//3]=min(x+b+d*y,x+(n-(n-y)//3)*d)
                q.append((n-y)//3)
            if (n+3-y)//3 not in dic or x+b+d*(3-y)<dic[(n+3-y)//3]:
                dic[(n+3-y)//3]=x+b+d*(3-y)
                q.append((n+3-y)//3)
            if n-y==0:
                dic[0]=min(dic[0],x+d*y)
        else:
            if n//3 not in dic or x+b<dic[n//3]:
                dic[n//3]=x+b
                q.append(n//3)
        if n%5:
            y=n-n//5*5
            if (n-y)//5 not in dic or min(x+c+d*y,x+(n-(n-y)//5)*d)<dic[(n-y)//5]:
                dic[(n-y)//5]=min(x+c+d*y,x+(n-(n-y)//5)*d)
                q.append((n-y)//5)
            if (n+5-y)//5 not in dic or x+c+d*(5-y)<dic[(n+5-y)//5]:
                dic[(n+5-y)//5]=x+c+d*(5-y)
                q.append((n+5-y)//5)
            if n-y==0:
                dic[0]=min(dic[0],x+d*y)
        else:
            if n//5 not in dic or x+c<dic[n//5]:
                dic[n//5]=x+c
                q.append(n//5)
    print(dic[0])

Solution (Python):
import sys
import collections
import heapq

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


INF = 1 << 62


def solve():
    N, A, B, C, D = nm()
    ans = D * N  
    mem = collections.defaultdict(lambda: INF)
    q = []
    heapq.heappush(q, (0, N))
    while q:
        coins, num = heapq.heappop(q)
        if mem[num] <= coins:
            continue
        mem[num] = coins
        if ans > num * D + coins:
            ans = num * D + coins
        if num == 0:
            continue
        tnum = num - (num % 2)
        heapq.heappush(q, (coins + (num - tnum) * D + A, tnum // 2))
        tnum = num + 2 - (num % 2)
        heapq.heappush(q, (coins + (tnum - num) * D + A, tnum // 2))

        tnum = num - (num % 3)
        heapq.heappush(q, (coins + (num - tnum) * D + B, tnum // 3))
        tnum = num + 3 - (num % 3)
        heapq.heappush(q, (coins + (tnum - num) * D + B, tnum // 3))

        tnum = num - (num % 5)
        heapq.heappush(q, (coins + (num - tnum) * D + C, tnum // 5))
        tnum = num + 5 - (num % 5)
        heapq.heappush(q, (coins + (tnum - num) * D + C, tnum // 5))

    return ans


def main():
    T = ni()
    for _ in range(T):
        print(solve())


main()

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

T = ri()
P = []
for i in range(T):
    P.append(rl())

import heapq

def solve(N, A, B, C, D):
    heap = []
    heapq.heappush(heap, (0, N))
    visited = {}

    while heap:
        
        c, n = heapq.heappop(heap)
        if n == 0:
            return c
        cands = [(A, 2), (B, 3), (C, 5), (D, 1)]
        for cost, div in cands:
            ncs = []
            if div == 1:
                next_n = 0
                next_c = D*n
                ncs.append((next_n, next_c))
            elif n % div == 0:
                next_n = n // div
                next_c = cost
                ncs.append((next_n, next_c))
            else:
                r = n % div
                next_n = (n-r) // div
                next_c = cost + r*D
                ncs.append((next_n, next_c))
                next_n = (n+r) // div
                next_c = cost + (div-r)*D
                ncs.append((next_n, next_c))
            for next_n, next_c in ncs:
                next_c += c
                if next_n in visited:
                    if visited[next_n] <= next_c:
                        continue
                visited[next_n] = next_c
                heapq.heappush(heap, (next_c, next_n))
    return -1

for p in P:
    ans = solve(*p)
    print(ans)

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

T = int(input())


@lru_cache(maxsize=None)
def dfs(n, A, B, C, D):
    
    ans = n * D

    for mul, pt in [(2, A), (3, B), (5, C)]:
        if n % mul == 0:
            n1 = n // mul
            a = dfs(n1, A, B, C, D) + pt
            ans = min(a, ans)
        elif mul <= n:
            md = n % mul
            n1 = (n - md) // mul
            n2 = (n + mul - md) // mul
            a = dfs(n1, A, B, C, D) + (D * md) + pt
            b = dfs(n2, A, B, C, D) + ((mul - md) * D) + pt
            ans = min(a, b, ans)

    return ans


def solve():
    N, A, B, C, D = map(int, input().split())

    ans = dfs(N, A, B, C, D)
    return ans


ans = []
for _ in range(T):
    t = solve()
    ans.append(t)

print("\n".join(map(str, ans)))

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

from heapq import *
def solve():
    n,a,b,c,d = [int(i) for i in readline().split()]

    ans = 10**18
    q = [(0,n)] 
    dic = {n:0}
    while q:
        cost,v = heappop(q)
        if dic[v] < cost: continue

        ans = min(ans,cost+d*v)
        for x in [2,3,5]:
            for y in range(-x+1,x):
                if (v+y)%x==0:
                    nv = (v+y)//x
                    nc = cost + d*abs(y) + a*(x==2) + b*(x==3) + c*(x==5)
                    if nv not in dic or nc < dic[nv]:
                        dic[nv] =  nc
                        heappush(q,(nc,nv))
                    

    print(ans)
    return



t = int(input())
for _ in range(t):
    solve()

Solution (Python):
from math import inf


def main(N, A, B, C, D):
    if N == 1:
        return D
    if N in dp:
        return dp[N]
    r = inf
    if N % 2 != 0:
        r = min(
            A + main(N // 2 + 1, A, B, C, D) + D,
            A + main(N // 2, A, B, C, D) + D,
            r
        )
    else:
        r = min(
            A + main(N // 2, A, B, C, D),
            r
        )
    if N % 3 != 0:
        r = min(
            B + main(N // 3 + 1, A, B, C, D) + (3 - N % 3) * D,
            B + main(N // 3, A, B, C, D) + (N % 3 * D),
            r
        )
    else:
        r = min(
            B + main(N // 3, A, B, C, D),
            r
        )
    if N % 5 != 0:
        r = min(
            C + main(N // 5 + 1, A, B, C, D) + (5 - N % 5) * D,
            C + main(N // 5, A, B, C, D) + (N % 5 * D),
            r
        )
    else:
        r = min(
            C + main(N // 5, A, B, C, D),
            r
        )
    r = min(N * D, r)
    dp[N] = r
    return r

T = int(input())
q_list = [[int(s) for s in input().split()] for _ in range(T)]
for q in q_list:
    dp = {0: 0}
    print(main(*q))

Solution (Python):
from functools import lru_cache

z = 0
n = 0
a = 0
b = 0
c = 0
d = 0

@lru_cache(maxsize=None)
def solve(x):
    global a
    global b
    global c
    global d

    if x==0:
        return 0
    if x==1:
        return d

    ans = d*x
    for p in [2,3,5]:
        m = x%p
        nxt = x//p
        A = a
        if p == 3:
            A = b
        if p == 5:
            A = c
        if nxt < x:
            cst = m*d + min(A, (nxt*p-nxt)*d) + solve(nxt)
            ans = min(ans, cst)
        nxt = (x+p-m)//p
        if nxt < x:
            cst = min((p-m)*d + A + solve(nxt), (x-nxt)*d + solve(nxt))
            ans = min(ans, cst)

    
    return ans

z = int(input())

for _ in range(z):
    n, a, b, c, d = map(int, input().split())
    print(solve(n))
    solve.cache_clear()

Solution (Python):
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D






T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    S = set()
    E = []
    Q = deque([N])
    while Q:
        x = deque.popleft(Q)
        if x in S: continue
        S.add(x)
        if x == 0: continue
        if x <= 10:
            nx = 0
            dd = D * x
            deque.append(Q, nx)
            E.append((x, nx, dd))
        if x % 2 == 0:
            nx = x // 2
            dd = min(A, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x > 1:
            nx = x // 2
            dd = min(A + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
            nx = x // 2 + 1
            dd = min(A + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        if x % 3 == 0:
            nx = x // 3
            dd = min(B, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x % 3 == 1:
            nx = x // 3
            dd = min(B + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        else:
            nx = x // 3 + 1
            dd = min(B + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        if x % 5 == 0:
            nx = x // 5
            dd = min(C, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x % 5 == 1:
            nx = x // 5
            dd = min(C + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 2:
            nx = x // 5
            dd = min(C + D * 2, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 3:
            nx = x // 5 + 1
            dd = min(C + D * 2, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 4:
            nx = x // 5 + 1
            dd = min(C + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
    
    
    A = []
    for a, b, d in E:
        A.append(a)
        A.append(b)
    A = sorted(list(set(A)))
    I = {a: i for i, a in enumerate(A)}
    E = [(I[a], I[b], d) for a, b, d in E]
    NN = len(A)
    
    EE = [[] for _ in range(NN)]
    for a, b, d in E:
        EE[a].append((b, d))
    print(dijkstra(NN, EE, I[N])[0])

Solution (Python):
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



T = int(sys.stdin.buffer.readline())
NABCD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(T)]


def solve2(N, A, B, C, D):
    heap = []
    dist = defaultdict(lambda: INF)
    dist[0] = 0
    dist[N] = D * N
    heapq.heappush(heap, (0, 0))
    while heap:
        cnt, n = heapq.heappop(heap)
        if dist[N] <= cnt:
            break
        if dist[n] < cnt:
            continue
        if n == N:
            break
        if n > N:
            dist[n] = cnt + abs(N - n)
        if cnt + A < dist[n * 2]:
            dist[n * 2] = cnt + A
            heapq.heappush(heap, (cnt + A, n * 2))
        if cnt + B < dist[n * 3]:
            dist[n * 3] = cnt + B
            heapq.heappush(heap, (cnt + B, n * 3))
        if cnt + C < dist[n * 5]:
            dist[n * 5] = cnt + C
            heapq.heappush(heap, (cnt + C, n * 5))
        if cnt + D < dist[n + 1]:
            dist[n + 1] = cnt + D
            heapq.heappush(heap, (cnt + D, n + 1))
        if cnt + D < dist[n - 1] and n - 1 > 0:
            dist[n - 1] = cnt + D
            heapq.heappush(heap, (cnt + D, n - 1))
    return dist[N]


def solve(N, A, B, C, D):
    dist = defaultdict(lambda: INF)
    dist[N] = 0
    
    heap = [(0, N)]
    while heap:
        cnt, n = heapq.heappop(heap)
        if dist[n] < cnt:
            continue
        if n <= 5:
            dist[0] = min(dist[0], cnt + n * D)

        if cnt + abs(n - n // 2) * D < dist[n // 2]:
            dist[n // 2] = cnt + abs(n - n // 2) * D
            heapq.heappush(heap, (cnt + abs(n - n // 2) * D, n // 2))
        if cnt + abs(n - n // 3) * D < dist[n // 3]:
            dist[n // 3] = cnt + abs(n - n // 3) * D
            heapq.heappush(heap, (cnt + abs(n - n // 3) * D, n // 3))
        if cnt + abs(n - n // 5) * D < dist[n // 5]:
            dist[n // 5] = cnt + abs(n - n // 5) * D
            heapq.heappush(heap, (cnt + abs(n - n // 5) * D, n // 5))

        l = n // 2 * 2
        d = A + abs(l - n) * D
        if A < abs(n - l // 2) * D and cnt + d < dist[l // 2]:
            dist[l // 2] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 2))
        r = l + 2
        d = A + abs(r - n) * D
        if A < abs(n - r // 2) * D and cnt + d < dist[r // 2]:
            dist[r // 2] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 2))

        l = n // 3 * 3
        d = B + abs(l - n) * D
        if B < abs(n - l // 3) * D and cnt + d < dist[l // 3]:
            dist[l // 3] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 3))
        r = l + 3
        d = B + abs(r - n) * D
        if B < abs(n - r // 3) * D and cnt + d < dist[r // 3]:
            dist[r // 3] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 3))

        l = n // 5 * 5
        d = C + abs(l - n) * D
        if C < abs(n - l // 5) * D and cnt + d < dist[l // 5]:
            dist[l // 5] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 5))
        r = l + 5
        d = C + abs(r - n) * D
        if C < abs(n - r // 5) * D and cnt + d < dist[r // 5]:
            dist[r // 5] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 5))

    return dist[0]


for r in NABCD:
    ans = solve(*r)
    print(ans)

Solution (Python):



import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

class Data:
    def __init__(self, a, b, c, d):
        self.A = a
        self.B = b
        self.C = c
        self.D = d

def solve(N, d, cache):
    if N in cache:
        return cache[N]

    if N == 0:
        return 0
    if N == 1:
        return d.D

    ans = d.D * N

    for (n, coeff) in ((2, d.A), (3, d.B), (5, d.C)):
        if N % n == 0:
            ans1 = coeff + solve(N // n, d, cache)
            ans = min(ans, ans1)
        else:
            left = N % n
            ans2 = d.D * left + coeff + solve((N - left) // n, d, cache)

            right = n - left
            ans3 = d.D * right + coeff + solve((N + right) // n, d, cache)

            ans = min(ans, ans2, ans3)

    cache[N] = ans
    return ans
    

def main():
    T = int(input())
    for t in range(T):
        N, A, B, C, D = map(int, input().split())
        d = Data(A, B, C, D)
        cache = {}
        print(solve(N, d, cache))


main()

Solution (Python):
from functools import lru_cache
inf = 10**18
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    @lru_cache(maxsize=None)
    def solve(N):
        
        if N==0:
            return 0
        elif N==1:
            return D
        elif N==2:
            return min(D*2, D+A)
        
        
        
        
        
        
        
        
        
        
        
        res = D*N
        for v, cost in zip([2,3,5], [A,B,C]):
            q, m = divmod(N, v)
            if m==0:
                res = min(res, solve(q)+cost)
            else:
                res = min(res, solve(q)+cost+m*D, solve(q+1)+cost+(v-m)*D)
        return res
    print(solve(N))

Solution (Python):

t=int(input())
for nt in range(t):
    n,a,b,c,d=[int(k) for k in input().strip().split(" ")]
    r={0:0}
    z=[0,0,a,b,0,c]
    steps=0
    def solve(k):
        
        global r
     
        if k in r:
            return r[k]
        else:
            res=k*d
            for i in [2,3,5]:
                if not k%i:
                    res=min(res,z[i]+solve(k//i))
                else:
                    res=min(res,solve(k//i)+z[i]+d*(k%i))
                    if (k//i+1)<k:
                        res=min(res,solve(k//i+1)+z[i]+d*(i-k%i))
     
     
        r[k]=res
        return res
    print(solve(n))

Solution (Python):
def main():
    import heapq
    t = int(input())
    for i in range(t):
        n, a, b, c, d = map(int, input().split())
        h = [(0, n)]
        heapq.heapify(h)
        s = set()
        while h:
            cost, now = heapq.heappop(h)
            if now in s:
                continue
            else:
                s.add(now)
            if now == 0:
                print(cost)
                break
            heapq.heappush(h, (cost+now*d, 0))
            
            if now % 2 == 0:
                heapq.heappush(h, (cost+a, now//2))
            else:
                heapq.heappush(h, (cost+a+d, (now+1)//2))
                heapq.heappush(h, (cost+a+d, now//2))
            
            if now % 3 == 0:
                heapq.heappush(h, (cost+b, now//3))
            else:
                temp = now % 3
                heapq.heappush(h, (cost+b+(3-temp)*d, (now+3-temp)//3))
                heapq.heappush(h, (cost+b+temp*d, now//3))
            
            if now % 5 == 0:
                heapq.heappush(h, (cost+c, now//5))
            else:
                temp = now % 5
                heapq.heappush(h, (cost+c+(5-temp)*d, (now+5-temp)//5))
                heapq.heappush(h, (cost+c+temp*d, now//5))


main()

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


t = read_int()
for case_num in range(t):
    n, a, b, c, d = read_ints()

    @lru_cache(None)
    def solve(t):
        if t == 0:
            return 0
        if t == 1:
            return d
        ans = d * t
        if t % 2 == 0:
            ans = min(ans, solve(t // 2) + a)
        else:
            ans = min(ans, solve(t // 2) + a + d, solve(t // 2 + 1) + a + d)

        if t % 3 == 0:
            ans = min(ans, solve(t // 3) + b)
        else:
            rem = t % 3
            ans = min(ans, solve(t // 3) + b + d * rem,
                      solve(t // 3 + 1) + b + (3 - rem) * d)

        if t % 5 == 0:
            ans = min(ans, solve(t // 5) + c)
        else:
            rem = t % 5
            ans = min(ans, solve(t // 5) + c + d * rem,
                      solve(t // 5 + 1) + c + (5 - rem) * d)
        return ans

    print(solve(n))

Solution (Python):
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
t=N()
INF=float("inf")
def f(n):
    if n in dp:
        return dp[n]
    r=INF
    for i,j in zip([2,3,5],[a,b,c]):
        x=(n//i)*i
        y=n-x
        r=min(r,f(x//i)+min(j+y*d,(n-x//i)*d))
        x=((n+i-1)//i)*i
        y=x-n
        r=min(r,f(x//i)+min(j+y*d,(n-x//i)*d))
    dp[n]=r
    return r
for i in range(t):
    dp=dict()
    n,a,b,c,d=NM()
    dp[2]=min(d*2,d+a)
    dp[1]=d
    dp[0]=0
    print(f(n))

Solution (Python):
import functools
def solve(N, A, B, C, D):
    @functools.lru_cache(None)
    def dp(N):
        if N<=0:
            return float('inf')
        if N == 1:
            return 0
        ans = (N-1)*D
        
        mod_2 = N % 2
        if not mod_2:
            ans = min(ans, dp(N//2)+A)
        else:
            ans =min(ans, dp((N+(2-mod_2))//2)+(A+D*(2-mod_2)))
            ans = min(dp((N-mod_2)//2)+(A+D*mod_2), ans)
        mod_3 = N % 3
        if not mod_3:
            ans = min(ans, dp(N//3)+B)
        else:
            ans =min(ans, dp((N+(3-mod_3))//3)+(B+D*(3-mod_3)))
            ans = min(dp((N-mod_3)//3)+(B+D*mod_3), ans)
        mod_5 = N % 5
        if not mod_5:
            ans = min(ans, dp(N//5)+C)
        else:
            ans =min(ans, dp((N+(5-mod_5))//5)+(C+D*(5-mod_5)))
            ans = min(dp((N-mod_5)//5)+(C+D*mod_5), ans)
        return ans
        
    return dp(N)+D
t = int(input())
for _ in range(t):
    N, A, B, C, D = list(map(int, input().split()))
    print(solve(N, A, B, C, D))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    INF = float('inf')
    mem = {}
    def solve(n):
        if n==0: return 0
        if n==1: return D
        if n in mem: return mem[n]
        tmp = n*D
        if n%2==0:
            tmp = min(tmp, solve(n//2) + A)
        else:
            tmp = min(tmp, solve(n//2) + A+D, solve(n//2+1) + A+D)
        if n%3==0:
            tmp = min(tmp, solve(n//3) + B)
        else:
            d = n%3
            u = 3-d
            tmp = min(tmp, solve(n//3) + B+d*D, solve(n//3+1) + B+u*D)
        if n%5==0:
            tmp = min(tmp, solve(n//5) + C)
        else:
            d = n%5
            u = 5-d
            tmp = min(tmp, solve(n//5) + C+d*D, solve(n//5+1) + C+u*D)
        mem[n] = tmp
        return tmp
    print(solve(N))

Solution (Python):
import sys

divs = [2, 3, 5]

t = int(input())

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]

    dp = {}

    def dfs(x):
        if x in dp:
            return dp[x]

        

        if x == 0:
            dp[x] = 0
            return dp[x]

        ret = x * d
        for i in range(-4, 5):
            if x - i < 0:
                continue

            nx = x - i
            for cost, div in zip(costs, divs):
                if nx % div != 0 or nx // div >= x:
                    continue

                ret = min(ret, dfs(nx // div) + cost + abs(i) * d)

        dp[x] = ret
        return ret

    print(dfs(n))

Solution (Python):
import sys
readline = sys.stdin.readline

INF = 10**30
def calc(k):
    if k in D:
        return D[k]
    if not k:
        return 0
    res = k*d
    if k != k//2 + 1:
        res = min(res, calc(k//2 + 1) + a + d*(2-k%2))
    if k != k//3 + 1:
        res = min(res, calc(k//3 + 1) + b + d*(3-k%3))
    if k != k//5 + 1:
        res = min(res, calc(k//5 + 1) + c + d*(5-k%5))
    
    if k >= 2:
        res = min(res, calc(k//2) + a + d*(k%2))
    if k >= 3:
        res = min(res, calc(k//3) + b + d*(k%3))
    if k >= 5:
        res = min(res, calc(k//5) + c + d*(k%5))
    D[k] = res
    return res
T = int(readline())
Ans = [None]*T
for qu in range(T):
    n, a, b, c, d = map(int, readline().split())
    D = dict()
    Ans[qu] = calc(n)
print('\n'.join(map(str, Ans)))

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(N, A, B, C, D):
    INF = 10**18

    @lru_cache(None)
    def f(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        ret = D * N
        q, r = divmod(N, 2)
        if r == 0:
            ret = min(ret, f(q) + A)
        else:
            ret = min(ret, f(q) + A + D, f(q + 1) + A + D)
        q, r = divmod(N, 3)
        if r == 0:
            ret = min(ret, f(q) + B)
        elif r == 1:
            ret = min(ret, f(q) + B + D)
        else:
            ret = min(ret, f(q + 1) + B + D)
        q, r = divmod(N, 5)
        if r == 0:
            ret = min(ret, f(q) + C)
        elif r == 1:
            ret = min(ret, f(q) + C + D)
        elif r == 2:
            ret = min(ret, f(q) + C + D + D)
        elif r == 3:
            ret = min(ret, f(q + 1) + C + D + D)
        else:
            ret = min(ret, f(q + 1) + C + D)
        return ret

    return f(N)

T = int(readline())
for _ in range(T):
    n, a, b, c, d = map(int, readline().split())
    print(solve(n, a, b, c, d))