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):
from heapq import heappush, heappop

T = int(input())

for i in range(T):
    N, A, B, C, D = map(int, input().split())
    h = [(0, N)]
    used = set()
    while h:
        cost, v = heappop(h)

        if v in used:
            continue

        if v == 1:
            print(cost + D)
            break

        used.add(v)

        d, m = divmod(v, 5)
        if d > 0:
            heappush(h, (cost + m * D + C, d))
        if m > 0:
            heappush(h, (cost + (5-m) * D + C, d+1))

        d, m = divmod(v, 3)
        if d > 0:
            heappush(h, (cost + m * D + B, d))
        if m > 0:
            heappush(h, (cost + (3-m) * D + B, d+1))

        d, m = divmod(v, 2)
        if d > 0:
            heappush(h, (cost + m * D + A, d))
        if m > 0:
            heappush(h, (cost + (2-m) * D + A, d+1))

        heappush(h, (cost + (v-1) * D, 1))

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

    memo = {}
    def dfs(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        if n in memo:
            return memo[n]
        res = min(
            d*n,
            d*((n+1)//2*2-n)+a+dfs((n+1)//2),
            d*(n-n//2*2)+a+dfs(n//2),
            d*((n+2)//3*3-n)+b+dfs((n+2)//3),
            d*(n-n//3*3)+b+dfs(n//3),
            d*((n+4)//5*5-n)+c+dfs((n+4)//5),
            d*(n-n//5*5)+c+dfs(n//5),
        )
        memo[n] = res
        return res

    print(dfs(n))

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

    memo = {}
    def dfs(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        if n in memo:
            return memo[n]
        res = min(
            d*n,
            d*((n+1)//2*2-n)+a+dfs((n+1)//2),
            d*(n-n//2*2)+a+dfs(n//2),
            d*((n+2)//3*3-n)+b+dfs((n+2)//3),
            d*(n-n//3*3)+b+dfs(n//3),
            d*((n+4)//5*5-n)+c+dfs((n+4)//5),
            d*(n-n//5*5)+c+dfs(n//5),
        )
        memo[n] = res
        return res

    print(dfs(n))

Solution (Python):
import sys
from functools import lru_cache
from bisect import bisect_left as lb, bisect_right as ub
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from math import gcd, ceil, sqrt
rd = lambda: int(sys.stdin.readline())
rds = lambda: map(int, sys.stdin.readline().split())
rdl = lambda: list(map(int, sys.stdin.readline().split()))
inf = 2 * 10 ** 18
sys.setrecursionlimit(10 ** 7)
rg = range
pr = print


T = rd()
for i in rg(T):
  n, a, b, c, d = rds()

  @lru_cache(maxsize=10 ** 7)
  def f(m):
    
    if m == 1:
      return d
    ret = d * m
    
    q, r = m // 2, m % 2
    if q:
      ret = min(ret, f(q) + d * r + a)
    if r:
      ret = min(ret, f(q + 1) + d * (2 - r) + a)

    q, r = m // 3, m % 3
    if q:
      ret = min(ret, f(q) + d * r + b)
    if r:
      ret = min(ret, f(q + 1) + d * (3 - r) + b)

    q, r = m // 5, m % 5
    if q:
      ret = min(ret, f(q) + d * r + c)
    if r:
      ret = min(ret, f(q + 1) + d * (5 - r) + c)
    return ret

  pr(f(n))

Solution (Python):


import sys
sys.setrecursionlimit(10**7)

T=int(input())



def saiki(n):

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

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
def f():
  n, a, b, c, d = map(int, input().split())
  dp = dict()
  def dfs(n):
    if n == 0:
      return 0
    if n == 1:
      return d
    if n in dp:
      return dp[n]
    res = n*d
    for s, k in ((a, 2), (b, 3), (c, 5)):
      q, r = divmod(n, k)
      res = min(res, dfs(q)+d*r+s)
      if r:
        res = min(res, dfs(q+1)+d*(k-r)+s)
    dp[n] = res
    return res
  ans = dfs(n)
  print(ans)
t = int(input())
for _ in range(t):
  f()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]
    
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x
    for div, cost in zip(divs, costs):
        dived = x//div
        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
        if x > div:
            dived = x//div+1
            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
    dp[x] = res
    return res
t = int(input())
for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {}
    dp[0] = 0
    dp[1] = d
    print(calc(n))

Solution (Python):
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007



def ggg(n,a,b,c,d):
	init = n
	open = queue.PriorityQueue()
	close = set()
	open.put((0, n))
	min_v = n*d
	while not open.empty():
		cost, pos = open.get()
		if pos in close:
			continue
		if cost > min_v:
			continue
		
		min_v = min(min_v, cost+pos*d)
		for c, add in zip([a,b,c],[2,3,5]):
			k = pos % add
			nc = cost + k*d + c
			np = pos // add
			if nc <= min_v and np not in close:
				open.put((nc, np))
				
			nnc = cost + (add-k) *d + c
			nnp = (pos + add) // add
			if nnc <= min_v and nnp not in close:
				open.put((nnc, nnp))
				
		close.add(pos)
	return min_v
		
		



def main():
	t = int(input())
	for i in range(t):
		n, a, b , c, d = tin()
		r = ggg(n,a,b,c,d)
		print(r)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N, E, memo):
    if N == 0:
        return 0
    
    if N == 1:
        return E[-1]

    if N in memo:
        return memo[N]

    res = N * E[-1]
    for k in (2, 3, 5):
        l = (N // k) * k
        r = ((N - 1) // k + 1) * k

        res = min(res, (N - l) * E[-1] + E[k] + f(l // k, E, memo))
        res = min(res, (r - N) * E[-1] + E[k] + f(r // k, E, memo))
    memo[N] = res
    return res
   

def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = read_values()
        E = (0, 0, A, B, 0, C, D)
        memo = dict()
        print(f(N, E, memo))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 9)

t = int(input())
a,b,c,d = 0,0,0,0
p = {}
INF = float('inf')

def calc(x):
  global a,b,c,d,p
  
  if x in p:
    return p[x]
  if x == 1:
    res = d
  else:
    res = INF
    if x%2 == 0:
      res = min(min(a,d*(x-x//2))+calc(x//2),res)
    else:
      res = min(min(a+d*(2-x%2),d*(x-(x+2-x%2)//2))+calc((x+2-x%2)//2),res)
      if x-x%2 > 0:
        res = min(min(a+d*(x%2),d*(x-(x-x%2)//2))+calc((x-x%2)//2),res)
    if x%3 == 0:
      res = min(min(b,d*(x-x//3))+calc(x//3),res)
    else:
      res = min(min(b+d*(3-x%3),d*(x-(x+3-x%3)//3))+calc((x+3-x%3)//3),res)
      if x-x%3 > 0:
        res = min(min(b+d*(x%3),d*(x-(x-x%3)//3))+calc((x-x%3)//3),res)
    if x%5 == 0:
      res = min(min(c,d*(x-x//5))+calc(x//5),res)
    else:
      res = min(min(c+d*(5-x%5),d*(x-(x+5-x%5)//5))+calc((x+5-x%5)//5),res)
      if x-x%5 > 0:
        res = min(min(c+d*(x%5),d*(x-(x-x%5)//5))+calc((x-x%5)//5),res)
  if x in p:
    p[x] = min(p[x],res)
  else:
    p[x] = res
  return res

def solve():
  global a,b,c,d,p
  n,a,b,c,d = map(int,input().split())
  p = {}
  
  
  print(min(calc(n),n*d))

for i in range(t):
  solve()

Solution (Python):
import sys

import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd



sys.setrecursionlimit(10**6)
t=int(input())
def cost(n):
    if n in dist:
        return dist[n]
    ret = min(
        D * n,
        D * abs(n - n//5*5) + C + cost(n//5),
        D * abs(n - (n+4)//5*5) + C + cost((n+4)//5),
        D * abs(n - n//3*3) + B + cost(n//3),
        D * abs(n - (n+2)//3*3) + B + cost((n+2)//3),
        D * abs(n - n//2*2) + A + cost(n//2),
        D * abs(n - (n+1)//2*2) + A + cost((n+1)//2)
    )

    dist[n]=ret
    return ret
for i in range(t):
    ans=0
    n,A,B,C,D=map(int,input().split())
    dist={0:0,1:D}
    print(cost(n))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def main():
    n, a, b, c, d = map(int, input().split())
    memo = {}
    def dfs(x):
        if x == 0:
            return 0
        elif x == 1:
            return d
        elif x in memo:
            return memo[x]
        else:
            ret = min(
                d * x,
                d * (x - x//2*2) + a + dfs(x//2),
                d * ((x+1)//2*2 - x) + a + dfs((x+1)//2),
                d * (x - x//3*3) + b + dfs(x//3),
                d * ((x+2)//3*3 - x) + b + dfs((x+2)//3),
                d * (x - x//5*5) + c + dfs(x//5),
                d * ((x+4)//5*5 - x) + c + dfs((x+4)//5)
            )
            memo[x] = ret
            return ret
    print(dfs(n))

t = int(input())
for i in range(t):
    main()

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def search(n, a, b, c, d):
    
    if n == 0:
        return 0
    if n == 1:
        return d
    if n in dic:
        return dic[n]

    ret = n * d

    tgt = n // 2
    ret = min(ret, search(tgt, a, b, c, d) + a + d * abs(tgt * 2 - n))
    tgt = (n + 1) // 2
    ret = min(ret, search(tgt, a, b, c, d) + a + d * abs(tgt * 2 - n))

    tgt = n // 3
    ret = min(ret, search(tgt, a, b, c, d) + b + d * abs(tgt * 3 - n))
    tgt = (n + 2) // 3
    ret = min(ret, search(tgt, a, b, c, d) + b + d * abs(tgt * 3- n))

    tgt = n // 5
    ret = min(ret, search(tgt, a, b, c, d) + c + d * abs(tgt * 5 - n))
    tgt = (n + 4) // 5
    ret = min(ret, search(tgt, a, b, c, d) + c + d * abs(tgt * 5 - n))

    dic[n] = ret
    return ret

def solve():
    N, A, B, C, D = getList()
    dic.clear()
    print(search(N, A, B, C, D))

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict

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

    memo = {0: 0, 1: D}

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

        memo[n] = ret
        return ret

    print(dfs(N))

Solution (Python):
def main():
    n , a , b , c , d = map(int,input().split())
    dic = {}
    def f(x):
        if x == 0:
            return 0
        elif x == 1:
            return d
        elif x in dic: 
            return dic[x]
        t1 = d*x                           
        t2 = d*(x%2)     + a + f(x//2)     
        t3 = d*(2-(x%2)) + a + f(-(-x//2)) 
        t4 = d*(x%3)     + b + f(x//3)     
        t5 = d*(3-(x%3)) + b + f(-(-x//3)) 
        t6 = d*(x%5)     + c + f(x//5)     
        t7 = d*(5-(x%5)) + c + f(-(-x//5)) 
        t = min(t1,t2,t3,t4,t5,t6,t7) 
        dic[x] = t 
        return t
    print(f(n))
    return
    
t = int(input())
for i in range(t):
    main()

Solution (Python):
from collections import defaultdict

def calc(n):
    if memo[n] != float('inf'):
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return D
    ans = n * D
    for x, c in [(2, A), (3, B), (5, C)]:
        ans = min(ans, calc(n//x) + c + (n % x) * D)
        if n % x:
            ans = min(ans, calc(n//x + 1) + c + (x - n % x) * D)
    memo[n] = ans
    return memo[n]


t = int(input())
for _ in range(t):
    N, A, B, C, D = map(int, input().split())
    memo = defaultdict(lambda: float('inf'))
    print(calc(N))

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	

def sol2(N,A,B,C,D):
	dM = dict({0: 0, 1: D})
	
	def dfs(n):
		if n in dM:
			return dM[n]

		res = min(
				D*n,
				D*(n%2) + A + dfs(n//2),
				D*(n%3) + B + dfs(n//3),
				D*(n%5) + C + dfs(n//5),
				D*(n%2) + A + dfs((n+1)//2),
				D*((3 - n%3)%3) + B + dfs((n+2)//3),
				D*((5 - n%5)%5) + C + dfs((n+4)//5)
			)

		dM[n] = res
		return res
	
	dfs(N)
	
	print(dM[N])


def main():
	T, = linput()
	for _ in "*"*T:
		sol2(*linput())

def ran():
	vRan = [random.randint(1,10) for _ in "*"*5]
	print(vRan)
	sol2(*vRan)

if __name__ == "__main__":
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	

def sol(N,A,B,C,D):
	res = inf
	at,bt,ct,dt = [0,]*4
	an,bn,cn,dn = [0,]*4
	cn = N
	for c in range(32):
		bn = cn
		for b in range(42):
			an = bn
			for a in range(63):
				dt = at+bt+ct+ an
				r = a*A+b*B+c*C+dt*D
				if res>r: print(a,b,c,dt,r)
				res = min(res, r)
				if not an: break
				at += an%2
				an = an//2
			at = 0
			bt += 0<bn%3
			bn = bn//3 + (bn%3==2)
		bt = 0
		cMod5 = cn%5
		ct += min(5-cMod5, cMod5)
		cn = cn//5 + (cMod5>2)
	
	print(res)

def sol2(N,A,B,C,D):
	dM = dict({0: 0, 1: D})
	
	def dfs(n):
		if n in dM.keys():
			return dM[n]

		res = min(
				D*n,
				D*(n%2) + A + dfs(n//2),
				D*(n%3) + B + dfs(n//3),
				D*(n%5) + C + dfs(n//5),
				D*(n%2) + A + dfs((n+1)//2),
				D*((3 - n%3)%3) + B + dfs((n+2)//3),
				D*((5 - n%5)%5) + C + dfs((n+4)//5)
			)

		dM[n] = res
		return res
	
	dfs(N)
	
	print(dM[N])


def main():
	T, = linput()
	for _ in "*"*T:
		sol2(*linput())

def ran():
	vRan = [random.randint(1,10) for _ in "*"*5]
	print(vRan)
	sol2(*vRan)

if __name__ == "__main__":
	main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)


def main():
    INF = float('INF')

    from collections import defaultdict, deque
    t = int(readline())

    for _ in range(t):
        n, a, b, c, d = map(int, readline().split())
        memo = defaultdict(lambda: INF)
        memo[n] = 0
        que = deque()
        que.append((n, 0))
        ans = n * d

        while que:
            cur, score = que.popleft()
            ans = min(ans, score + cur*d)

            if cur == 0:
                continue

            if cur % 2 == 0:
                if score + a < memo[cur // 2] and a < cur // 2 * d:
                    memo[cur // 2] = score + a
                    que.append((cur // 2, score + a))
            else:
                diff1 = cur % 2
                diff2 = 2 - diff1
                nx1 = (cur - diff1) // 2
                nx2 = (cur + diff2) // 2
                cost1 = a + diff1 * d
                cost2 = a + diff2 * d
                if score + cost1 < memo[nx1]:
                    memo[nx1] = score + cost1
                    que.append((nx1, score + cost1))
                if score + cost2 < memo[nx2]:
                    memo[nx2] = score + cost2
                    que.append((nx2, score + cost2))

            if cur % 3 == 0:
                if score + b < memo[cur // 3] and b < 2 * cur // 3 * d:
                    memo[cur // 3] = score + b
                    que.append((cur // 3, score + b))
            else:
                diff1 = cur % 3
                diff2 = 3 - diff1
                nx1 = (cur - diff1) // 3
                nx2 = (cur + diff2) // 3
                cost1 = b + diff1 * d
                cost2 = b + diff2 * d
                if score + cost1 < memo[nx1]:
                    memo[nx1] = score + cost1
                    que.append((nx1, score + cost1))
                if score + cost2 < memo[nx2]:
                    memo[nx2] = score + cost2
                    que.append((nx2, score + cost2))

            if cur % 5 == 0:
                if score + c < memo[cur // 5] and c < 4 * cur // 5 * d:
                    memo[cur // 5] = score + c
                    que.append((cur // 5, score + c))
            else:
                diff1 = cur % 5
                diff2 = 5 - diff1
                nx1 = (cur - diff1) // 5
                nx2 = (cur + diff2) // 5
                cost1 = c + diff1 * d
                cost2 = c + diff2 * d
                if score + cost1 < memo[nx1]:
                    memo[nx1] = score + cost1
                    que.append((nx1, score + cost1))
                if score + cost2 < memo[nx2]:
                    memo[nx2] = score + cost2
                    que.append((nx2, score + cost2))

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from collections import defaultdict
import math
t = int(input())
def solve(n):
    if dist[n] != float('inf'):
        return dist[n]
    if n == 0:
        return 0
    if n == 1:
        return d
    ans = float('inf')
    for x,cost in ([5,c],[3,b],[2,a]):
        e = 0
        if n%x:
            e = 1 
        y = n%x
        ans = min(ans,solve(n//x) + cost + (e*d*y))

        if e ==1:
            ans = min(ans,solve(n//x+1) + cost + ((x-y)*d))
    dist[n] = min(ans,n*d)   
    return dist[n]

for i in range(t):
    n,a,b,c,d, = list(map(int,input().split()))
    dist = defaultdict(lambda: float('inf'))
    print(solve(n))

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import defaultdict
from heapq import *

def main():
	t=II()
	while t:
		t-=1
		n,a,b,c,d=MI()
		Q=[-n,0]
		heapify(Q)
		D=defaultdict(lambda:10**18)
		D[n]=0
		k=n+1
		while Q:
			now=-heappop(Q)
			
			if now==0:
				print(D[0])
				break

			if now<k:
				q2,r2=divmod(now,2)
				q3,r3=divmod(now,3)
				q5,r5=divmod(now,5)

				
				if D[q5]>D[now]+c+r5*d:
					D[q5]=D[now]+c+r5*d
					heappush(Q,-q5)
				if r5!=0 and D[q5+1]>D[now]+c+(5-r5)*d:
					D[q5+1]=D[now]+c+(5-r5)*d
					heappush(Q,-q5-1)

				if D[q3]>D[now]+b+r3*d:
					D[q3]=D[now]+b+r3*d
					heappush(Q,-q3)
				if r3!=0 and D[q3+1]>D[now]+b+(3-r3)*d:
					D[q3+1]=D[now]+b+(3-r3)*d
					heappush(Q,-q3-1)

				if D[q2]>D[now]+a+r2*d:
					D[q2]=D[now]+a+r2*d
					heappush(Q,-q2)
				if r2!=0 and D[q2+1]>D[now]+a+(2-r2)*d:
					D[q2+1]=D[now]+a+(2-r2)*d
					heappush(Q,-q2-1)

				D[0]=min(D[0],D[now]+now*d)







if __name__ == "__main__":
	main()

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import defaultdict
from heapq import *

def main():
	t=II()
	while t:
		t-=1
		n,a,b,c,d=MI()
		Q=[-n,0]
		heapify(Q)
		D=defaultdict(lambda:10**18)
		D[n]=0
		k=n+1
		while Q:
			now=-heappop(Q)
			
			if now==0:
				print(D[0])
				break

			if now<k:
				q2,r2=divmod(now,2)
				q3,r3=divmod(now,3)
				q5,r5=divmod(now,5)

				
				if D[q5]>D[now]+c+r5*d:
					D[q5]=D[now]+c+r5*d
					heappush(Q,-q5)
				if r5!=0 and D[q5+1]>D[now]+c+(5-r5)*d:
					D[q5+1]=D[now]+c+(5-r5)*d
					heappush(Q,-q5-1)

				if D[q3]>D[now]+b+r3*d:
					D[q3]=D[now]+b+r3*d
					heappush(Q,-q3)
				if r3!=0 and D[q3+1]>D[now]+b+(3-r3)*d:
					D[q3+1]=D[now]+b+(3-r3)*d
					heappush(Q,-q3-1)

				if D[q2]>D[now]+a+r2*d:
					D[q2]=D[now]+a+r2*d
					heappush(Q,-q2)
				if r2!=0 and D[q2+1]>D[now]+a+(2-r2)*d:
					D[q2+1]=D[now]+a+(2-r2)*d
					heappush(Q,-q2-1)

				D[0]=min(D[0],D[now]+now*d)







if __name__ == "__main__":
	main()

Solution (Python):
import math
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
        elif n == 1:
            return D
        elif 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):
from functools import lru_cache
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def solve():
    N, a, b, c, d = map(int, input().split())

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

    print(F(N))


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

Solution (Python):
memo = dict()


def calc(n):
    if n == 0:
        return 0
    if n == 1:
        return d
    if n in memo:
        return memo[n]

    ret = min(n * d,
              a + calc(n//2) + (n % 2) * d,
              a + calc((n+1)//2) + ((2 - (n % 2)) % 2) * d,
              b + calc(n//3) + (n % 3) * d,
              b + calc((n+2)//3) + ((3 - (n % 3)) % 3) * d,
              c + calc(n//5) + (n % 5) * d,
              c + calc((n+4)//5) + ((5 - (n % 5)) % 5) * d)

    memo[n] = ret
    return ret


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

Solution (Python):



T = int(input())
from collections import deque
INF = 10**18

def transit(n, i, p):
    if p == 1:
        num = ((n+(i-1))//i)*i
        cos = d * (num - n)
        num //= i
        cos += ci[i]
    else:
        num = (n//i)*i
        cos = d * (n - num)
        num //= i
        cos += ci[i]
    return (num, cos)

for _ in range(T):
    N, a2, a3, a5, d = map(int, input().split())
    ci = {}
    ci[2]=a2
    ci[3]=a3
    ci[5]=a5
    dp = {}
    def cost(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        if n in dp:
            return dp[n]
        ret = n * d
        for i in [2,3,5]:
            num, cos = transit(n, i, 1)
            ret = min(ret, cos + cost(num))
            num, cos = transit(n, i, -1)
            ret = min(ret, cos + cost(num))
        dp[n] = ret
        return ret
    print(cost(N))

Solution (Python):
class Solver:
    def __init__(self, n, a, b, c, d):
        self.n = n
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.dc = {}

    def coin(self, n):

        if n == 0:
            return 0
        elif n == 1:
            return self.d
        elif n == -1:
            return self.d
        elif n in self.dc.keys():
            return self.dc[n]
        else:
            coin1 = n * self.d
            coin2 = min(
                (n % 2) * self.d + self.a + self.coin((n - n % 2) // 2),
                ((-n) % 2) * self.d + self.a + self.coin((n + (-n) % 2) // 2),
            )
            coin3 = min(
                (n % 3) * self.d + self.b + self.coin((n - n % 3) // 3),
                ((-n) % 3) * self.d + self.b + self.coin((n + (-n) % 3) // 3),
            )
            coin5 = min(
                (n % 5) * self.d + self.c + self.coin((n - n % 5) // 5),
                ((-n) % 5) * self.d + self.c + self.coin((n + (-n) % 5) // 5),
            )
            result = min([coin2, coin3, coin5, coin1])
            self.dc[n] = result
            return result

    def solve(self):
        return self.coin(self.n)






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

for n, a, b, c, d in q:
    answer = Solver(n, a, b, c, d).solve()
    print(answer)

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

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

    M={0:0,1:D}
    S={2:A,3:B,5:C}
    
    def f(N):
        if N in M:
            return M[N]
        
        R=D*N
        for k in S:
            p,q=N//k*k,(N+k-1)//k*k
            R=min(R,
                  D*abs(N-p)+S[k]+f(p//k),
                  D*abs(N-q)+S[k]+f(q//k)
                  )

        M[N]=R
        return R

    X.append(f(N))
print("\n".join(map(str,X)))

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

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

    M={0:0,1:D}
    S={2:A,3:B,5:C}
    
    def f(N):
        if N in M:
            return M[N]
        
        R=D*N
        for k in S:
            p,q=N//k*k,(N+k-1)//k*k
            R=min(R,
                  D*abs(N-p)+S[k]+f(p//k),
                  D*abs(N-q)+S[k]+f(q//k)
                  )

        M[N]=R
        return R

    X.append(f(N))
print("\n".join(map(str,X)))

Solution (Python):
import math, collections, heapq
T = int(input())


def solve(N, A, B, C, D):
    dp = collections.defaultdict(lambda: float('inf'))
    dp[0] = 0
    dp[1] = D

    def calc(x):
        if x in dp:
            return dp[x]
        cand = []
        q, r = divmod(x, 2)
        if r == 1:
            cand += [calc(x // 2) + min(A + D, D * (x - x // 2))]
            cand += [calc(x // 2 + 1) + min(A + D, D * (x - x // 2 - 1))]
        else:
            cand += [calc(x // 2) + min(A, D * (x - x // 2))]
        q, r = divmod(x, 3)
        if r < 2:
            cand += [calc(x // 3) + min(B + D * r, D * (x - x // 3))]
        else:
            cand += [calc(x // 3 + 1) + min(B + D, D * (x - x // 3 - 1))]
        q, r = divmod(x, 5)
        if r < 3:
            cand += [calc(x // 5) + min(C + D * r, D * (x - x // 5))]
        else:
            cand += [
                calc(x // 5 + 1) + min(C + D * (5 - r), D * (x - x // 5 - 1))
            ]
        dp[x] = min(cand)
        return dp[x]

    print(calc(N))


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