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())
l=[list(map(int,input().split())) for i in range(t)]
from collections import defaultdict

def solve(n):
    if n==1:
        return d
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]

    ret = []
    ret.append(d*n)

    if n%2==0:
        ret.append(a + solve(n//2))
    else:
        ret.append(d + a + solve((n+1)//2))
        ret.append(d + a + solve((n-1)//2))

    if n%3==0:
        ret.append(b + solve(n//3))
    else:
        if (n+1)%3==0:
            ret.append(d + b + solve((n+1)//3))
        else:
            ret.append(d + b + solve((n-1)//3))

    if n%5==0:
        ret.append(c + solve(n//5))
    else:
        if (n-2)%5==0:
            ret.append(2*d + c + solve((n-2)//5))
        elif (n-1)%5==0:
            ret.append(d + c + solve((n-1)//5))
        elif (n+1)%5==0:
            ret.append(d + c + solve((n+1)//5))
        elif (n+2)%5==0:
            ret.append(2*d + c + solve((n+2)//5))

    memo[n]=min(ret)

    return min(ret)

for tmp in l:
    n,a,b,c,d=tmp

    memo=defaultdict(lambda: -1)
    ans = solve(n)
    print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10000)

T = int(input())
a = [list(map(int,input().split())) for _ in range(T)]
memo = {}


def solve(N,A,B,C,D):
    if N==0:
        return 0
    if N==1:
        return D
    if N in memo:
        return memo[N]
    ans = min(
        D*N,
        (N-2*(N//2))*D+A+solve(N//2,A,B,C,D),
        (2*((N+1)//2)-N)*D+A+solve((N+1)//2,A,B,C,D),
        (N-3*(N//3))*D+B+solve(N//3,A,B,C,D),
        (3*((N+2)//3)-N)*D+B+solve((N+2)//3,A,B,C,D),
        (N-5*(N//5))*D+C+solve(N//5,A,B,C,D),
        (5*((N+4)//5)-N)*D+C+solve((N+4)//5,A,B,C,D),
    )
    memo[N] = ans
    return ans

for i in range(T):
    memo = {}
    (N,A,B,C,D) = a[i]
    print(solve(N,A,B,C,D))

Solution (Python):
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(input())):
    n,a,b,c,d=map(int,input().split())
    dp={}
    print(solve())
if __name__ == "__main__":
  main()

Solution (Python):
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(input())):
    n,a,b,c,d=map(int,input().split())
    dp={}
    print(solve())
if __name__ == "__main__":
  main()

Solution (Python):

MEMO = {}

def solve(N, A, B, C, D):
    
    
    
    

    if N == 0:
        return 0
    elif N == 1:
        return D
    elif N in MEMO:
        return MEMO[N]
    
    
    
    
    
    
    
    
    
    

    min_score = D * N 

    
    
    
    
    

    
    
    
    
    

    
    
    
    
    

    
    
    div_score = {2: A, 3: B, 5: C}

    for d, s in div_score.items():
        div1 = N // d
        div2 = (N + d - 1) // d
        min_score = min(min_score, solve(div1, A, B, C, D) + s + D * abs(N - d * div1))
        min_score = min(min_score, solve(div2, A, B, C, D) + s + D * abs(N - d * div2))

    
    
    MEMO[N] = min_score
    return min_score


def main():
    T = int(input())
    queries = []
    for t in range(T):
        queries.append(list(map(int, input().split())))
    
    ans = []
    for N, A, B, C, D in queries:
        MEMO.clear()
        ans.append(solve(N, A, B, C, D))

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

if __name__ == '__main__':
    main()

Solution (Python):
def examA():
    T = I()
    ans = [inf]*T
    for t in range(T):
        N, A, B, C, D = LI()
        num = [[2,A],[3,B],[5,C]]
        dp = defaultdict(lambda: inf)
        dp[N] = 0
        que = deque()
        que.append(N)
        while(que):
            now = que.pop()
            if now==0:
                continue
            cur = dp[now] + D*now
            if cur<dp[0]:
                dp[0] = cur
            cur = dp[now]
            for n,K in num:
                curn = cur + (now % n) * D + K
                if curn < dp[(now - now % n) // n]:
                    dp[(now - now % n) // n] = curn
                    que.append((now - now % n) // n)
                curn_ = cur + (-now % n) * D + K
                if curn_ < dp[(now + (-now % n)) // n]:
                    dp[(now + (-now % n)) // n] = curn_
                    que.append((now + (-now % n)) // n)
        ans[t] = dp[0]
    for v in ans:
        print(v)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return


import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examA()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import heapq

T = int(input())
for t in range(T):
    N,A,B,C,D = map(int,input().split())
    q = [(0,N)]
    heapq.heapify(q)
    seen = set()
    while q:
        cost, n = heapq.heappop(q)
        if n in seen:
            continue
        seen.add(n)
        if n == 0:
            print(cost)
            break

        heapq.heappush(q, (cost + n * D, 0))
        if n % 2 ==0:
            heapq.heappush(q, (cost + A, n // 2))
        else: 
            heapq.heappush(q, (cost + D + A, (n + 1) // 2))
            heapq.heappush(q, (cost + D + A, (n - 1) // 2))
        if n % 3 ==0:
            heapq.heappush(q, (cost + B, n // 3))
        else:
            rest = n % 3
            heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
            heapq.heappush(q, (cost + (3-rest) * D + B, (n - rest + 3) // 3))

        if n % 5 ==0:
            heapq.heappush(q, (cost + C, n // 5))
        else:
            rest = n % 5
            heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
            heapq.heappush(q, (cost + (5-rest) * D + C, (n - rest + 5) // 5))

Solution (Python):
from decimal import Decimal
import math
import sys
sys.setrecursionlimit(10**9)


t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())

    memo = dict()
    memo[0] = 0
    memo[1] = d

    def solve(v):
        if v in memo:
            return memo[v]

        if v > 10**16:
            v = Decimal(v)

        memo[v] = min(solve(math.floor(v / 5)) + c + (v - math.floor(v / 5) * 5) * d,
                      solve(math.ceil(v / 5)) + c + (math.ceil(v / 5) * 5 - v) * d,
                      solve(math.floor(v / 3)) + b + (v - math.floor(v / 3) * 3) * d,
                      solve(math.ceil(v / 3)) + b + (math.ceil(v / 3) * 3 - v) * d,
                      solve(math.floor(v / 2)) + a + (v - math.floor(v / 2) * 2) * d,
                      solve(math.ceil(v / 2)) + a + (math.ceil(v / 2) * 2 - v) * d,
                      v * d)
        return memo[v]

    print(solve(n))

Solution (Python):
t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    e = {}
    def coin(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        if n in e:
            return e[n]
        f = min(
            d*n,
            d*abs(n-n//5*5)+c+coin(n//5),
            d*abs(n-(n+4)//5*5)+c+coin((n+4)//5),
            d*abs(n-n//3*3)+b+coin(n//3),
            d*abs(n-(n+2)//3*3)+b+coin((n+2)//3),
            d*abs(n-n//2*2)+a+coin(n//2),
            d*abs(n-(n+1)//2*2)+a+coin((n+1)//2)
        )
        e[n] = f
        return f
    print(coin(n))

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

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

 
for i in range(t):
    N = l[i][0]
    A = l[i][1]
    B = l[i][2]
    C = l[i][3]
    D = l[i][4]
    @lru_cache(maxsize=10**18)
    def min_coin(n):
        if(n == 0):
            return 0
        elif(n == 1):
            return D
        else:
            if(n%2 == 0):
                a = min_coin(n//2)
            else:
                a = min(min_coin(n//2)+D,min_coin(n//2+1)+D)
            if(n%3 == 0):
                b = min_coin(n//3)
            elif(n%3 == 1):
                b = min(min_coin(n//3)+D,min_coin(n//3+1)+D*2)
            else:
                b = min(min_coin(n//3)+D*2,min_coin(n//3+1)+D)
            if(n%5 == 0):
                c = min_coin(n//5)
            else:
                re = n%5
                c = min(min_coin(n//5)+D*re,min_coin(n//5+1)+D*(5-re))
            return min(a+A,b+B,c+C,D*n)   
    print(int(min_coin(N)))

Solution (Python):
from collections import defaultdict


def calc(case):
    
    N, A, B, C, D = case
    memo = defaultdict(int)
    x = N
    def dp(n):
        if n == 0:
            return 0
        elif n == 1:
            return D
        elif n == 2:
            return D + min([A, D])
        for k in [2, 3, 5]:
            for i in [0, 1]:
                if memo[n // k + i] == 0:
                    memo[n // k + i] = dp(n // k + i)
        ret = min([
            n * D, 
            A + (n % 2) * D + memo[n // 2],
            A + (2 - n % 2) * D + memo[n // 2 + 1],
            B + (n % 3) * D + memo[n // 3],
            B + (3 - n % 3) * D + memo[n // 3 + 1],
            C + (n % 5) * D + memo[n // 5],
            C + (5 - n % 5) * D + memo[n // 5 + 1]
        ])
        return ret
    return dp(N)


def main():
    T = int(input())
    cases = [list(map(int, input().split())) for _ in range(T)]
    for case in cases:
        print(calc(case))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict,deque
class dfs:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.memory = defaultdict(int)
        self.Q = deque([[self.N,0]])
    def dfs(self):
        while self.Q:
            num,cost = self.Q.popleft()
            if self.memory[num] > cost :
                pass
            else:
                if num == 0:
                    self.ans = min(self.ans,cost)
                elif num == 1:
                    self.ans = min(self.ans,cost+self.D)
                else:
                    for step,a_cost in [[2,self.A],[3,self.B],[5,self.C]]:
                        if num % step != 0:
                            temp_num = (num//step)+1
                            temp_cost = cost + (((num//step)+1)*step - num) * self.D + a_cost
                            self.memo_check_append(temp_num,temp_cost)
                        temp_num = num//step
                        temp_cost = cost + (num - (num//step)*step) * self.D + a_cost
                        self.memo_check_append(temp_num,temp_cost)
                    self.ans = min(self.ans,cost + num * self.D)
        return self.ans
    def memo_check_append(self,n,c):
        if self.memory[n] > c or self.memory[n] == 0:
            self.Q.append([n,c])
            self.memory[n] = c

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    t = I()
    aa = [LI() for _ in range(t)]

    rr = []
    for n,a,b,c,dd in aa:
        e = {2: a, 3: b, 5: c}
        def search(s, t):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if u == t:
                    break
                if v[u]:
                    continue
                v[u] = True

                if d[t] > k + dd * (u-t):
                    d[t] = k + dd * (u-t)
                for ek, ev in e.items():
                    m = u % ek
                    if m == 0:
                        if d[u//ek] > k + ev:
                            d[u//ek] = k + ev
                            heapq.heappush(q, (k+ev, u//ek))
                    else:
                        if d[u//ek + 1] > k + ev + (ek - m) * dd:
                            d[u//ek + 1] = k + ev + (ek - m) * dd
                            heapq.heappush(q, (k + ev + (ek - m) * dd, u//ek + 1))
                        if d[u//ek] > k + ev + m * dd:
                            d[u//ek] = k + ev + m * dd
                            heapq.heappush(q, (k + ev + m * dd, u//ek))

            return d[t]

        rr.append(search(n, 1) + dd)

    return JA(rr, "\n")

print(main())

Solution (Python):
from collections import defaultdict
import heapq

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


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            if checking%kake == 0:
                devided1 = checking//kake
                devided2 = checking//kake
            else:
                devided1 = checking//kake
                devided2 = checking//kake + 1
                
            
            
            
            added_cost1 = cost + abs(devided1*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(devided2*kake-checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    print(memo[0])

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
INF = float("inf")
t = int(input())

def dfs(x):
    if x == 0: return 0
    if x == 1: return d
    if x in memo: return memo[x]
    r2, r3, r5 = x % 2, x % 3, x % 5
    res = d*x
    res = min(dfs(x//2) + c2+r2*d, res)
    if r2: res = min(dfs((x+2)//2) + c2+(2-r2)*d, res)
    res = min(dfs(x//3) + c3+r3*d, res)
    if r3: res = min(dfs((x+3)//3) + c3+(3-r3)*d, res)
    res = min(dfs(x//5) + c5+r5*d, res)
    if r5: res = min(dfs((x+5)//5) + c5+(5-r5)*d, res)
    memo[x] = res
    return res

for _ in range(t):
    memo = dict()
    n, c2, c3, c5, d = map(int, input().split())
    print(dfs(n))

Solution (Python):
T = int(input())

for t in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}

    def dist(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo:
            return memo[n]
        
        ret = min(
            D * n,
            D * abs(n - n//5*5) + C + dist(n//5),
            D * abs(n - (n+4)//5*5) + C + dist((n+4)//5),
            D * abs(n - n//3*3) + B + dist(n//3),
            D * abs(n - (n+2)//3*3) + B + dist((n+2)//3),
            D * abs(n - n//2*2) + A + dist(n//2),
            D * abs(n - (n+1)//2*2) + A + dist((n+1)//2)
        )

        memo[n] = ret
        return ret
    print(dist(N))

Solution (Python):
def dfs(n):
    if n == 1:
        return d
    if n == 0:
        return 0
    if n in dic:
        return dic[n]
    ans = min(n * d, dfs(n // 2) + a + (n % 2) * d, dfs((n + 1) // 2) + a + ((-1 * n) % 2) * d, dfs(n // 3) + b + (n % 3) * d, dfs((n + 2) // 3) + b + ((-1 * n) % 3) * d, dfs(n // 5) + c + (n % 5) * d, dfs((n + 4) // 5) + c + ((-1 * n) % 5) * d)
    dic[n] = ans
    return ans
t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    dic = dict()
    print(dfs(n))

Solution (Python):
from heapq import heappop, heappush

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

    Q = [(0, N)]
    
    S = set()
    an = D * N
    while Q:
        cost, num = heappop(Q)
        if num in S:
            continue
        an = min(an, cost + num * D)
        if num == 1:
            break
        S.add(num)

        q, r = divmod(num, 2)
        if r < 2:
            heappush(Q, (cost + A + r * D, q))
        if r > 0:
            heappush(Q, (cost + A + (2 - r) * D, q + 1))

        q, r = divmod(num, 3)
        if r < 2:
            heappush(Q, (cost + B + r * D, q))
        if r > 1:
            heappush(Q, (cost + B + (3 - r) * D, q + 1))

        q, r = divmod(num, 5)
        if r < 3:
            heappush(Q, (cost + C + r * D, q))
        if r > 2:
            heappush(Q, (cost + C + (5 - r) * D, q + 1))
    ans.append(an)

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

Solution (Python):
from heapq import heappop, heappush

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

    Q = [(0, N)]
    
    S = set()
    an = D * N
    while Q:
        cost, num = heappop(Q)
        if num in S:
            continue
        an = min(an, cost + num * D)
        if num == 1:
            break
        S.add(num)

        q, r = divmod(num, 2)
        if r < 2:
            heappush(Q, (cost + A + r * D, q))
        if r > 0:
            heappush(Q, (cost + A + (2 - r) * D, q + 1))

        q, r = divmod(num, 3)
        if r < 2:
            heappush(Q, (cost + B + r * D, q))
        if r > 0:
            heappush(Q, (cost + B + (3 - r) * D, q + 1))

        q, r = divmod(num, 5)
        if r < 3:
            heappush(Q, (cost + C + r * D, q))
        if r > 0:
            heappush(Q, (cost + C + (5 - r) * D, q + 1))
    ans.append(an)

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

Solution (Python):
from heapq import heapify, heappop, heappush
from collections import defaultdict
Inf = 10**28
inpl = lambda: list(map(int,input().split()))
T = int(input())
for _ in range(T):
    N, A, B, C, D = inpl()
    visited = defaultdict(lambda: Inf)
    ans = Inf
    pool = [(0,N)] 
    while pool:
        c, n = heappop(pool)
        if c >= ans:
            break
        elif c > visited[n]:
            continue
        q = c + D*n
        if q < ans:
            ans = q

        for mag, cost in [(2,A), (3,B), (5,C)]:
            m = (n+mag//2)//mag
            q = c + abs(n - mag*m)*D + cost
            if q < ans and q < visited[m]:
                visited[m] = q
                heappush(pool, (q, m))

    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def min2(x, y): return x if x <= y else y

def rec(x):
    if x not in memo:
        ans = D*x
        for d, cost in zip([2, 3, 5], [A, B, C]):
            x2 = x//d
            if x2 != x:
                ans = min2(ans, x%d*D + cost + rec(x2))
            if x%d:
                x2 = (x+d-1)//d
                if x2 != x:
                    ans = min2(ans, (d-x%d)*D + cost + rec(x2))
        memo[x] = ans
    return memo[x]

anss = []
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}
    ans = rec(N)
    anss.append(ans)

print('\n'.join(map(str, anss)))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

def solve(n,a,b,c,d):
    
    @lru_cache(None)
    def f(n):
        if n==0: return 0
        elif n==1: return d
        ret=d*n
        q,r=n//2, n%2
        if r==0:
            ret=min(f(q)+a, ret)
        else:
            ret=min(ret, f(q)+a+d*r, f(q+1)+a+d*r)
        q,r=n//3, n%3
        if r==0:
            ret=min(f(q)+b, ret)
        else:
            ret=min(ret, f(q)+b+d*r, f(q+1)+b+d*(3-r))
        q,r=n//5, n%5
        if r==0:
            ret=min(f(q)+c, ret)
        else:
            ret=min(ret, f(q)+c+d*r, f(q+1)+c+d*(5-r))
        return ret
    
    return f(n)

if __name__=='__main__':
    t=int(input())
    for _ in range(t):
        n,a,b,c,d=map(int,input().split())
        print(solve(n,a,b,c,d))

Solution (Python):
import sys
import heapq
T = int(input())
from collections import deque
for t in range(T):
  N,A,B,C,D = map(int,input().split())
  q = [(0, N)]
  heapq.heapify(q)
  seen = set()
  while q:
    cost,n = heapq.heappop(q)
    if n in seen:
      continue
    seen.add(n)
    if n == 0:
      print(cost)
      break

    heapq.heappush(q, (cost + n * D, 0))
    if n % 2 == 0:
      heapq.heappush(q, (cost + A, n // 2))
    else:
      heapq.heappush(q, (cost + D + A, (n + 1) // 2))
      heapq.heappush(q, (cost + D + A, (n - 1) // 2))

    if n % 3 == 0:
      heapq.heappush(q, (cost + B, n // 3))
    else:
      rest = n % 3
      heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
      heapq.heappush(q, (cost + (3 - rest) * D + B, (n - rest + 3) // 3))

    if n % 5 == 0:
      heapq.heappush(q, (cost + C, n // 5))
    else:
      rest = n % 5
      heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
      heapq.heappush(q, (cost + (5 - rest) * D + C, (n - rest + 5) // 5))

Solution (Python):


"""
    Author : thekushalghosh
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()


    
def solve():
    n,a,b,c,d = invr()
    memo = {}
    def qw(n):
        if n == 0:
            return 0
 
        if n == 1:
            return d
 
        if n in memo:
            return memo[n]
 
        ret = n * d
 
        if (n % 2 == 0):
            ret = min(ret, a + qw(n // 2))
        else:
            ret = min(ret, (n%2)*d + a + qw(n // 2), (2-n%2)*d + a + qw((n+(2-n%2))//2))
 
        if (n % 3 == 0):
            ret = min(ret, b + qw(n // 3))
        else:
            ret = min(ret, (n%3)*d + b + qw(n // 3), (3-n%3)*d + b + qw((n+(3-n%3))//3))
 
        if (n % 5 == 0):
            ret = min(ret, c + qw(n // 5))
        else:
            ret = min(ret, (n%5)*d + c + qw(n // 5), (5-n%5)*d + c + qw((n+(5-n%5))//5))
        memo[n] = ret
        return ret
    print(qw(n))
        



def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    t = inp()
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
    sys.stdout.close()

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

Solution (Python):
T = int(input())

while(T > 0):
    N, A, B, C, D = map(int, input().split())
    memo = {}
    def d(n):
        if n == 0:
            return 0

        if n == 1:
            return D

        if n in memo:
            return memo[n]

        ret = n * D

        if (n % 2 == 0):
            ret = min(ret, A + d(n // 2))
        else:
            ret = min(ret, (n%2)*D + A + d(n // 2), (2-n%2)*D + A + d((n+(2-n%2))//2))

        if (n % 3 == 0):
            ret = min(ret, B + d(n // 3))
        else:
            ret = min(ret, (n%3)*D + B + d(n // 3), (3-n%3)*D + B + d((n+(3-n%3))//3))

        if (n % 5 == 0):
            ret = min(ret, C + d(n // 5))
        else:
            ret = min(ret, (n%5)*D + C + d(n // 5), (5-n%5)*D + C + d((n+(5-n%5))//5))

        memo[n] = ret
        return ret

    print(d(N))
    T -= 1

Solution (Python):
import sys

a = 0
b = 0
c = 0
d = 0
pw = dict()

def minCost(n):
	if n == 0:
		return 0
	if n == 1:
		return d
	if n in pw:
		return pw[n]
	else:
		ns = dict()
		ns[(n // 2) * 2] = 1
		ns[((n + 1) // 2) * 2] = 1
		ns[(n // 3) * 3] = 1
		ns[((n + 2) // 3) * 3] = 1
		ns[(n // 5) * 5] = 1
		ns[((n + 4) // 5) * 5] = 1
		_min = n * d
		for key in ns:
			if key % 2 == 0:
				_min = min(_min, a + int(minCost(key // 2)) + d * abs(n - key))
			if key % 3 == 0:
				_min = min(_min, b + int(minCost(key // 3)) + d * abs(n - key))
			if key % 5 == 0:
				_min = min(_min, c + int(minCost(key // 5)) + d * abs(n - key))
		pw[n] = _min
		return pw[n]

t = int(sys.stdin.readline())
for i in range(0, t):
	line = sys.stdin.readline().split()
	n = int(line[0])
	a = int(line[1])
	b = int(line[2])
	c = int(line[3])
	d = int(line[4])
	pw = dict()
	print(int(minCost(n)))

Solution (Python):
import sys
readline = sys.stdin.readline
 
import heapq
T = int(readline())
from collections import deque
for t in range(T):
  N,A,B,C,D = map(int,readline().split())
  q = [(0, N)]
  heapq.heapify(q)
  seen = set()
  while q:
    cost,n = heapq.heappop(q)
    if n in seen:
      continue
    seen.add(n)
    if n == 0:
      print(cost)
      break
      
    heapq.heappush(q, (cost + n * D, 0))
    if n % 2 == 0:
      heapq.heappush(q, (cost + A, n // 2))
    else:
      heapq.heappush(q, (cost + D + A, (n + 1) // 2))
      heapq.heappush(q, (cost + D + A, (n - 1) // 2))
      
    if n % 3 == 0:
      heapq.heappush(q, (cost + B, n // 3))
    else:
      rest = n % 3
      heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
      heapq.heappush(q, (cost + (3 - rest) * D + B, (n - rest + 3) // 3))
      
    if n % 5 == 0:
      heapq.heappush(q, (cost + C, n // 5))
    else:
      rest = n % 5
      heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
      heapq.heappush(q, (cost + (5 - rest) * D + C, (n - rest + 5) // 5))