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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve(N):
	if N == 0:
		return 0
	if N == 1:
		return D

	if memo[N]:
		return memo[N]

	ret = N*D
	
	up = 2*(-(-N//2))
	down = 2*(N//2)
	ret = min(ret, D*(up-N)+A+solve(up//2))
	ret = min(ret, D*(N-down)+A+solve(down//2))

	up = 3*(-(-N//3))
	down = 3*(N//3)
	
	ret = min(ret, D*(up-N)+B+solve(up//3))
	ret = min(ret, D*(N-down)+B+solve(down//3))

	up = 5*(-(-N//5))
	down = 5*(N//5)
	ret = min(ret, D*(up-N)+C+solve(up//5))
	ret = min(ret, D*(N-down)+C+solve(down//5))

	memo[N] = ret
	return ret

T = INT()
ans = []
for _ in range(T):
	N, A, B, C, D = MAP()
	memo = defaultdict(int)
	ans.append(solve(N))
print(*ans, sep="\n")

Solution (Python):
from sys import stdin
input = stdin.readline
import copy as cp
from collections import deque, OrderedDict

LINF = 1001002003004005006
INF = 1001001001

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

A = 0
B = 0
C = 0
D = 0

mp = OrderedDict({})

def dfs(N):
  global A, B, C, D

  if N in mp:
    return mp[N]

  cost = LINF
  if LINF//D > N:
    cost = D * N

  l = N//2*2
  r = l+2
  if (l//2 < N):
    cost = min(cost, A+(N-l)*D+dfs(l//2))
  if (r//2 < N):
    cost = min(cost, A+(r-N)*D+dfs(r//2))

  l = N//3*3
  r = l+3
  if (l//3 < N):
    cost = min(cost, B+(N-l)*D+dfs(l//3))
  if (r//3 < N):
    cost = min(cost, B+(r-N)*D+dfs(r//3))

  l = N//5*5
  r = l+5
  if (l//5 < N):
    cost = min(cost, C+(N-l)*D+dfs(l//5))
  if (r//5 < N):
    cost = min(cost, C+(r-N)*D+dfs(r//5))

  mp[N] = cost
  return cost


T = int(input().rstrip())

for _ in range(T):
  N, A, B, C, D = map(int, input().rstrip().split())
  mp.clear()
  mp[0] = 0
  mp[1] = D
  ans = dfs(N)
  print(ans)

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

Solution (Python):
import sys
from collections import defaultdict as dd
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
for _ in range(int(input())):
  N, A, B, C, D = map(int, input().split())
  h = [(0, N)]
  d = dd(lambda: float("inf"))
  d[N] = 0
  vis = set()
  while len(h):
    c, x = hpop(h)
    if x in vis: continue
    vis.add(x)
    if x == 0:
      print(c)
      break
    
    if d[0] <= c: continue
    hpush(h, (c + x * D, 0))
    d[0] = min(d[0], c + x * D)
    if d[x // 2] > c + A + (x % 2) * D:
      hpush(h, (c + A + (x % 2) * D, x // 2))
      d[x // 2] = c + A + (x % 2) * D
    if d[-(-x // 2)] > c + A + (x % 2) * D:
      hpush(h, (c + A + (-x % 2) * D, -(-x // 2)))
      d[-(-x // 2)] = c + A + (-x % 2) * D

    if d[x // 3] > c + B + (x % 3) * D:
      hpush(h, (c + B + (x % 3) * D, x // 3))
      d[x // 3] = c + B + (x % 3) * D
    if d[-(x // 3)] > c + B + (-x % 3) * D:
      hpush(h, (c + B + (-x % 3) * D, -(-x // 3)))
      d[-(-x // 3)] = c + B + (-x % 3) * D

    if d[x // 5] > c + C + (x % 5) * D:
      hpush(h, (c + C + (x % 5) * D, x // 5))
      d[x // 5] = c + C + (x % 5) * D
    if d[x // 5] > c + C + (-x % 5) * D:
      hpush(h, (c + C + (-x % 5) * D, -(-x // 5)))
      d[-(-x // 5)] = c + C + (-x % 5) * D

Solution (Python):
import sys
readline = sys.stdin.readline
 
import heapq
  
T = int(readline())
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
    if n == 0:
      print(cost)
      break
    seen.add(n)
    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 + (3 - rest)) // 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 + (5 - rest)) // 5))

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

import heapq
  
T = int(readline())
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
    if n == 0:
      print(cost)
      break
    seen.add(n)
    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 + (3 - rest)) // 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 + (5 - rest)) // 5))

Solution (Python):
import sys
import math
from collections import deque
input = sys.stdin.readline


def solve(N,A,B,C,D):
    
    dp = {}
    
    def dfs(n):
        if n in dp:
            return dp[n]
        if n<=0:
            return 0
        if n==1:
            return D
        
        R = n*D
        
        
        R = min(R,A+D*(n%2)+dfs(n//2))
        
        
        if n%2 != 0:
            R = min(R,A+D*(2-n%2)+dfs((n+2-1)//2))
        
        
        
        R = min(R,B+D*(n%3)+dfs(n//3))
        
        
        if n%3 != 0:
            R = min(R,B+D*(3-n%3)+dfs((n+3-1)//3))
        
        
        
        R = min(R,C+D*(n%5)+dfs(n//5))
        
        
        if n%5 != 0:
            R = min(R,C+D*(5-n%5)+dfs((n+5-1)//5))
        
        
        dp[n]=R
        return R
    
    return dfs(N)
    

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

Solution (Python):
def solve(N, A, B, C, D, memo):
    if N in memo:
        return memo[N]
    ans = D * N
    if N <= 1:
        memo[N] = ans
        return ans
    divs = [(2, A), (3, B), (5, C)]
    for divider, divcost in divs:
        delta = N % divider
        if delta:
            ans = min(ans, solve(N // divider, A, B, C, D, memo) +
                      divcost + D * delta)
            ans = min(ans, solve(N // divider + 1, A, B, C, D, memo) +
                      divcost + D * (divider - delta))
        else:
            ans = min(ans, solve(N // divider, A, B, C, D, memo) + divcost)
    memo[N] = ans
    return ans


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


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
t=int(input())
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    dp=dict()
    dp[n]=0
    que=[[0,n]] 

    def dp_revise(x,v):
        if x not in dp.keys():
            dp[x]=v
            return True
        elif dp[x]>v:
            dp[x]=v
            return True
        else: 
            return False

    while que:
        p=heapq.heappop(que)
        if p[1]==0: 
            break
        x=p[1]
        r2=x%2
        v=min(a+r2*d, d*(x//2+r2))+dp[x] 
        if dp_revise(x//2,v):
            heapq.heappush(que,[v,x//2])
        if r2!=0:
            v=min(a+d, d+d*(x//2+1))+dp[x] 
            if dp_revise(x//2+1,v):
                heapq.heappush(que,[v,x//2+1])
        r3=x%3
        v=min(b+r3*d, d*(x//3)*2+r3*d)+dp[x] 
        if dp_revise(x//3,v):
            heapq.heappush(que,[v,x//3])
        if r3!=0:
            v=min(b+(3-r3)*d, d*(x//3+1)*2+(3-r3)*d)+dp[x] 
            if dp_revise(x//3+1,v):
                heapq.heappush(que,[v,x//3+1])
        r5=x%5
        v=min(c+r5*d, d*(x//5)*4+r5*d)+dp[x] 
        if dp_revise(x//5,v):
            heapq.heappush(que,[v,x//5])
        if r5!=0:
            v=min(c+(5-r5)*d, d*(x//5+1)*4+(5-r5)*d)+dp[x] 
            if dp_revise(x//5+1,v):
                heapq.heappush(que,[v,x//5+1])
            
    print(dp[0])

Solution (Python):
'''
5
29384293847243 454353412 332423423 934923490 1
'''
import sys
import heapq
from collections import defaultdict
read = sys.stdin.buffer.read

N, *r = map(int, read().split())
r=iter(r)
Querys=zip(r,r,r,r,r)

cost=defaultdict(lambda :10**27)
que=0
ans=0
def push(n,c):
    global ans
    if n not in cost:
        heapq.heappush(que,(c,n))
    cost[n]=min(cost[n],c)
    ans=min(ans,c+n*d)
    
for n,a,b,c,d in Querys:
    cost.clear()
    cost[n]=0
    ans=n*d
    que=[(0,n)]

    
    while que:
        C,n=heapq.heappop(que)
        C=cost[n]
        if n==1 or cost[n]<C:
            continue
        
        if n%2==0:
            push(n//2,C+a)
        else:
            push(n//2,C+a+d)
            push(n//2+1,C+a+d)
        
        if n<3:
            continue
        if n%3==0:
            push(n//3,C+b)
        if n%3==1:
            push(n//3,C+b+d)
        if n%3==2:
            push(n//3+1,C+b+d)
        
        if n<5:
            continue
        if n%5==0:
            push(n//5,C+c)
        if n%5==1:
            push(n//5,C+c+d)
        if n%5==2:
            push(n//5,C+c+2*d)
        if n%5==3:
            push(n//5+1,C+c+2*d)
        if n%5==4:
            push(n//5+1,C+c+d)
    print(ans)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
t = int(input())
memo = dict()
def calc(n):
    global a,b,c,d
    
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    elif n == 1:
        return d
    res = d * n
    
    if n % 2 == 0:
        res = min(res, calc(n//2) + a)
    else:
        res = min(res, calc((n + 1)//2) + a + d, calc((n - 1)//2) + a + d)
    
    if n % 3 == 0:
        res = min(res, calc(n//3) + b)
    else:
        res = min(res, calc((n - (n % 3))//3) + b + d * (n % 3),
         calc((n + (3 - (n % 3)))//3) + b + d * (3 - (n % 3)))

    
    if n % 5 == 0:
        res = min(res, calc(n//5) + c)
    else:
        res = min(res, calc((n - (n % 5))//5) + c + d * (n % 5),
         calc((n + (5 - (n % 5)))//5) + c + d * (5 - (n % 5)))
    memo[n] = res
    
    return memo[n]

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    print(calc(n))
    memo = dict()

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

def f(N, A, B, C, D):
  if N == 0:
    return 0
  elif N == 1:
    return D
  elif N in data:
    return data[N]
  else:
    cost = min(
      D * N,
      D * abs(N - (N // 2) * 2) + A + f(N//2, A, B, C, D),
      D * abs(N - ((N + 1)// 2) * 2) + A + f((N + 1)// 2, A, B, C, D),
      D * abs(N - (N // 3) * 3) + B + f(N//3, A, B, C, D),
      D * abs(N - ((N + (N % 3)) // 3) * 3) + B + f((N + (N % 3)) // 3, A, B, C, D),
      D * abs(N - (N // 5) * 5) + C + f(N//5, A, B, C, D),
      D * abs(N - ((N + (N % 5)) // 5) * 5) + C + f((N + (N % 5))//5, A, B, C, D)
    )
    data[N] = cost
    return cost
  
for _ in range(T):
  N, A, B, C, D = list(map(int, input().split()))
  data = {}
  print(f(N, A, B, C, D))

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

while(T > 0):
    N, A, B, C, D = map(int, input().split())
    dp = {}

    def d(n):
        if n == 0:
            return 0
        if n == 1:
            return D

        if n in dp:
            return dp[n]

        ret = min(
            D * n,
            D * abs(n - (n // 2) * 2) + A + d(n // 2),
            D * abs(n - ((n+1) // 2) * 2) + A + d((n+1) // 2),
            D * abs(n - (n // 3) * 3) + B + d(n // 3),
            D * abs(n - ((n + 2) // 3) * 3) + B + d((n + 2) // 3),
            D * abs(n - (n // 5) * 5) + C + d(n // 5),
            D * abs(n - ((n + 4) // 5) * 5) + C + d((n + 4) // 5),
        )

        dp[n] = ret
        return ret

    print(d(N))
    T -= 1

Solution (Python):
from collections import deque
from collections import defaultdict
import math

def solve(n):
    q = deque()
    q.append(n)
    
    dist = defaultdict(lambda: float('inf'))
    dist[n] = 0
    while len(q):
        m = q.popleft()

        if m == 0:
            continue
        if m == 1:
            if dist[0] > dist[1] + d:
                dist[0] = dist[1] + d
                continue
        
        
        for x,cost in ([5,c],[3,b],[2,a]):

            y = m%x 
            e = 1 if y else 0 
            
            hiyou = min((n-(m//x))*d,dist[m]+cost+(e*d*y),dist[m]+ (m-(m//x))*d)
            if dist[m//x] > hiyou:
                q.append(m//x)
                dist[m//x] = hiyou

            
            hiyou = min((n-(m//x)+1)*d,dist[m]+cost+((x-y)*d),dist[m]+ (m-(m//x-1))*d)
            if e and dist[m//x+1]> hiyou:
                q.append(m//x+1)
                dist[m//x+1] = hiyou
    

    return dist[0]


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

Solution (Python):
import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def rec(u):
    if dist[u] != INF:
        return dist[u]
    if u == 0:
        return 0
    res = abs(u)*d
    if u >= 5:
        x = u % 5
        v = (u-x) // 5
        res = min(res, rec(v) + c+d*x)
        if u % 5 != 0:
            x = 5 - u % 5
            v = (u+x) // 5
            res = min(res, rec(v) + c+d*x)
    if u >= 3:
        x = u % 3
        v = (u-x) // 3
        res = min(res, rec(v) + b+d*x)
        if u % 3 != 0:
            x = 3 - u % 3
            v = (u+x) // 3
            res = min(res, rec(v) + b+d*x)
    if u >= 2:
        x = u % 2
        v = (u-x) // 2
        res = min(res, rec(v) + a+d*x)
        if u % 2 != 0:
            x = 2 - u % 2
            v = (u+x) // 2
            res = min(res, rec(v) + a+d*x)
    dist[u] = res
    return res

for _ in range(INT()):
    N, a, b, c, d = MAP()

    dist = defaultdict(lambda: INF)
    ans = rec(N)
    print(ans)

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


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


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

    cmin = N * D
    cache = dict()
    cache[0] = 0
    cache[1] = D
    cache[2] = min(D+D, D+A)
    
    def dfs(n):
        if n in cache:
            return cache[n]
        c = n * D
        c = min(c, dfs(n//2) + A + (n%2) * D)
        c = min(c, dfs(n//2+1) + A + ((-n-1)%2+1) * D)
        c = min(c, dfs(n//3) + B + (n%3) * D)
        c = min(c, dfs(n//3+1) + B + ((-n-1)%3+1) * D)
        c = min(c, dfs(n//5) + C + (n%5) * D)
        c = min(c, dfs(n//5+1) + C + ((-n-1)%5+1) * D)
        cache[n] = c
        return c
    
    return min(cmin, dfs(N))


if __name__ == '__main__':
    T = int(input().strip())
    for i in range(T):
        inputs = read()
        outputs = solve(*inputs)
        if outputs is not None:
            print("{}".format(outputs))

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def dijkstra(src):
    from heapq import heappush, heappop
    from collections import defaultdict

    que = [(0, src)]
    dist = defaultdict(lambda: INF)
    dist[src] = 0
    while que:
        cost, u = heappop(que)
        dist[0] = min(dist[0], cost+abs(u)*d)
        if u >= 5:
            x = u % 5
            v = (u-x) // 5
            if cost+c+d*x < dist[v]:
                dist[v] = cost+c+d*x
                heappush(que, (cost+c+d*x, v))
            if u % 5 != 0:
                x = 5 - u % 5
                v = (u+x) // 5

                if cost+c+d*x < dist[v]:
                    dist[v] = cost+c+d*x
                    heappush(que, (cost+c+d*x, v))
        if u >= 3:
            x = u % 3
            v = (u-x) // 3
            if cost+b+d*x < dist[v]:
                dist[v] = cost+b+d*x
                heappush(que, (cost+b+d*x, v))
            if u % 3 != 0:
                x = 3 - u % 3
                v = (u+x) // 3
                if cost+b+d*x < dist[v]:
                    dist[v] = cost+b+d*x
                    heappush(que, (cost+b+d*x, v))
        if u >= 2:
            x = u % 2
            v = (u-x) // 2
            if cost+a+d*x < dist[v]:
                dist[v] = cost+a+d*x
                heappush(que, (cost+a+d*x, v))
            if u % 2 != 0:
                x = 2 - u % 2
                v = (u+x) // 2
                if cost+a+d*x < dist[v]:
                    dist[v] = cost+a+d*x
                    heappush(que, (cost+a+d*x, v))
    return dist

for _ in range(INT()):
    N, a, b, c, d = MAP()

    res = dijkstra(N)
    ans = res[0]
    print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def dijkstra(src):
    from heapq import heappush, heappop

    que = [(0, src)]
    dist = {}
    dist[src] = 0
    while que:
        cost, u = heappop(que)
        if 0 not in dist or dist[0] > cost+abs(u)*d:
            dist[0] =  cost+abs(u)*d
        if u >= 5:
            x = u % 5
            v = (u-x) // 5
            if v not in dist or cost+c+d*x < dist[v]:
                dist[v] = cost+c+d*x
                heappush(que, (cost+c+d*x, v))
            if u % 5 != 0:
                x = 5 - u % 5
                v = (u+x) // 5
                if v not in dist or cost+c+d*x < dist[v]:
                    dist[v] = cost+c+d*x
                    heappush(que, (cost+c+d*x, v))
        if u >= 3:
            x = u % 3
            v = (u-x) // 3
            if v not in dist or cost+b+d*x < dist[v]:
                dist[v] = cost+b+d*x
                heappush(que, (cost+b+d*x, v))
            if u % 3 != 0:
                x = 3 - u % 3
                v = (u+x) // 3
                if v not in dist or cost+b+d*x < dist[v]:
                    dist[v] = cost+b+d*x
                    heappush(que, (cost+b+d*x, v))
        if u >= 2:
            x = u % 2
            v = (u-x) // 2
            if v not in dist or cost+a+d*x < dist[v]:
                dist[v] = cost+a+d*x
                heappush(que, (cost+a+d*x, v))
            if u % 2 != 0:
                x = 2 - u % 2
                v = (u+x) // 2
                if v not in dist or cost+a+d*x < dist[v]:
                    dist[v] = cost+a+d*x
                    heappush(que, (cost+a+d*x, v))
    return dist

for _ in range(INT()):
    N, a, b, c, d = MAP()

    res = dijkstra(N)
    ans = res[0]
    print(ans)

Solution (Python):
T = int(input())
for _ in range(T):
  N,a,b,c,d = map(int, input().split())
  
  memo = {}
  def solve(n):
    if n == 0:
      return 0
    if n == 1:
      return d
    if n in memo:
      return memo[n]
    tmp = n * d
    if n % 2 == 0:
      tmp = min(tmp, a + solve(n//2))
    else:
      tmp =  min(tmp, a + d + solve(n//2), a + d + solve(n//2+1))
    if n % 3 == 0:
      tmp = min(tmp, b + solve(n//3))
    else:
      ret1 = n % 3
      ret2 = 3 - ret1
      tmp = min(tmp, b + d*ret1 + solve(n//3), b + d*ret2 + solve(n//3+1))
    if n % 5 == 0:
      tmp = min(tmp, c + solve(n//5))
    else:
      ret1 = n % 5
      ret2 = 5 - ret1
      tmp = min(tmp, c + d*ret1 + solve(n//5), c + d*ret2 + solve(n//5+1))
    memo[n] = tmp
    return memo[n]
    
  print(solve(N))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

minCoin = 0
N = 0
A = 0
B = 0
C = 0
D = 0
memo = []

def main():
    T = int(input())
    for _ in range(T):
        global minCoin,N,A,B,C,D,memo
        N,A,B,C,D  = map(int, input().split()) 
        memo = {}
        minCoin = N*D
        bfs(N,0)
        print(minCoin)

def bfs(tempX,tempC):
    global minCoin,N,A,B,C,D,memo
    if(tempC>=minCoin):
        return
    
    minCoin = min(tempC+(D*tempX),minCoin)

    if(tempX==1):
        return

    if(tempX in memo):
        if tempC < memo[tempX]:
            memo[tempX] = tempC
        else:
            return
    else:
        memo[tempX] = tempC


    if(tempX%2==0):
        bfs(tempX//2,tempC+A)
    else:
        bfs((tempX+1)//2,tempC+A+D)
        bfs((tempX-1)//2,tempC+A+D)
    if(tempX%3==0):
        bfs(tempX//3,tempC+B)
    else:
        mod = tempX%3
        bfs((tempX-mod+3)//3,tempC+B+(D*(3-mod)))
        bfs((tempX-mod)//3,tempC+B+(D*mod))
    if(tempX%5==0):
        bfs(tempX//5,tempC+C)
    else:
        mod = tempX%5
        bfs((tempX-mod+5)//5,tempC+C+(D*(5-mod)))
        bfs((tempX-mod)//5,tempC+C+(D*mod))





if __name__ == '__main__':
    main()

Solution (Python):

v={}
def rec(n,a,b,c,d):
    if n in v:
        return v[n]
    x=float('inf')
    if n==0:
        return 0
    if n==1:
        return d
    x=n*d
    if n%2==0:
            x=min(x,rec(n//2,a,b,c,d)+a)
    else:
            low=n//2
            up=n//2+1
            x=min(x,rec(low,a,b,c,d)+d*(n-low*2)+a)
            x=min(x,rec(up,a,b,c,d)+d*(up*2-n)+a)
    if n%3==0:
            x=min(x,rec(n//3,a,b,c,d)+b)
    else:
            low=n//3
            up=n//3+1
            x=min(x,rec(low,a,b,c,d)+d*(n-low*3)+b)
            x=min(x,rec(up,a,b,c,d)+d*(up*3-n)+b)
    if n%5==0:
            x=min(x,rec(n//5,a,b,c,d)+c)
    else:
            low=n//5
            up=n//5+1
            x=min(x,rec(low,a,b,c,d)+d*(n-low*5)+c)
            x=min(x,rec(up,a,b,c,d)+d*(up*5-n)+c)
    v[n]=x
    return x

for _ in range(int(input())):
    n,a,b,c,d=map(int,input().split())
    print(rec(n,a,b,c,d))
    v={}

Solution (Python):
_, *e = [[*map(int, t.split())] for t in open(0)]

for n, a, b, c, d in e:
    mem = {0: 0, 1: d}
    mult_cost = {2: a, 3: b, 5: c}

    def solve(n):
        if n not in mem:
            tmp = n*d
            for k in mult_cost:
                if n % k == 0:
                    tmp = min(tmp, solve(n//k) + mult_cost[k])
                else:
                    tmp = min(tmp, solve(
                        n//k) + mult_cost[k] + (n % k)*d, solve(n//k + 1) + mult_cost[k] + k*d - (n % k)*d)
            mem[n] = tmp
        return mem[n]

    print(solve(n))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = 10**20

def solve(N,A,B,C,D):
    memo = dict()
    def rec(n):
        if n in memo:
            return memo[n]
        elif n==0:
            return 0
        elif n==1:
            return D
        
        ret = D * n
        if n%2==0:
            ret = min(ret, rec(n//2)+A)
        else:
            ret = min(ret, rec(n//2)+A+D, rec(n//2+1)+A+D)
        
        if n%3==0:
            ret = min(ret, rec(n//3)+B)
        else:
            ret = min(ret, rec(n//3)+B+D*(n%3), rec(n//3+1)+B+D*(3-n%3))
        
        if n%5==0:
            ret = min(ret, rec(n//5)+C)
        else:
            ret = min(ret, rec(n//5)+C+D*(n%5), rec(n//5+1)+C+D*(5-n%5))
        
        memo[n] = ret
        return ret    
    return rec(N)

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

for a in answer:
    print(a)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

T = int(input())


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


    def f(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo.keys():
            return memo[n]

        ret = 1 << 100
        ret = min(ret, f(n // 2) + (n - n // 2 * 2) * D + A, f(n // 2) + (n - n // 2) * D)
        ret = min(ret, f(n // 3) + (n - n // 3 * 3) * D + B, f(n // 3) + (n - n // 3) * D)
        ret = min(ret, f(n // 5) + (n - n // 5 * 5) * D + C, f(n // 5) + (n - n // 5) * D)
        ret = min(ret, f((n + 1) // 2) + ((n + 1) // 2 * 2 - n) * D + A, f((n + 1) // 2) + (n - (n + 1) // 2) * D)
        ret = min(ret, f((n + 2) // 3) + ((n + 2) // 3 * 3 - n) * D + B, f((n + 2) // 3) + (n - (n + 2) // 3) * D)
        ret = min(ret, f((n + 4) // 5) + ((n + 4) // 5 * 5 - n) * D + C, f((n + 4) // 5) + (n - (n + 4) // 5) * D)
        memo[n] = ret
        return ret

    print(f(N))

Solution (Python):


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