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
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {}
    def f(x):
        if x in memo:
            return memo[x]
        if x == 0:
            return 0
        if abs(x) == 1:
            return d

        ans = [x * d]
        if x % 2 == 0:
            ans.append(f(x // 2) + a)
        else:
            ans.append(f((x+1) // 2) + a + d)
            ans.append(f((x-1) // 2) + a + d)

        if x % 3 == 0:
            ans.append(f(x // 3) + b)
        elif x % 3 == 1:
            ans.append(f((x-1) // 3) + b + d)
        elif x % 3 == 2:
            ans.append(f((x+1) // 3) + b + d)

        if x % 5 == 0:
            ans.append(f(x // 5) + c)
        elif x % 5 == 1:
            ans.append(f((x-1) // 5) + c + d)
        elif x % 5 == 2:
            ans.append(f((x-2) // 5) + c + 2 * d)
        elif x % 5 == 3:
            ans.append(f((x+2) // 5) + c + 2 * d)
        elif x % 5 == 4:
            ans.append(f((x+1) // 5) + c + d)

        memo[x] = min(ans)
        return memo[x]

    print(f(n))

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)


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


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


        @lru_cache(maxsize=None)
        def calc(N):
            if N == 0:
                return 0
            if N == 1:
                return D

            cost = N * D
            
            for T, Tcost in ((2, A), (3, B), (5, C)):
                div, mod = divmod(N, T)

                cost = min(cost, calc(div) + Tcost + mod * D)
                if mod:
                    cost = min(cost, calc(div + 1) + Tcost + (T - mod) * D)

            return cost


        return calc(N)


    for TESTCASE in TESTCASEs:
        total_cost = calc_cost(*TESTCASE)
        print(total_cost)


if __name__ == '__main__':
    main()

sys.exit()

Solution (Python):
T=int(input())
for i in range(T):
  N,a,b,c,d=map(int, input().split())
  memo={}
  memo[0]=0
  memo[1]=d
  
  def f(n):
    if n in memo:
      return memo[n]
    e2,e3,e5=n%2,n%3,n%5
    dd=min(d*n,d*e2+a+f((n-e2)//2),d*e2+a+f((n+e2)//2),d*e3+b+f((n-e3)//3),d*(3-e3)+b+f((n+3-e3)//3),d*e5+c+f((n-e5)//5),d*(5-e5)+c+f((n+5-e5)//5))
    memo[n]=dd
    return dd
  print(f(N))

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

    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):
from collections import defaultdict
def f(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,f(n//x)+c+n%x*D)
        if n%x:
            ans=min(ans,f(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(f(N))

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):
def pay(n, a, b, c, d):
    ops = ((2, a), (3, b), (5, c))
    dp = {0:0, 1:d, 2:d + min(a, d)}
    
    def helper(n):
        if n in dp:
            return dp[n]
        
        m = min(op[1] + min(helper(n//op[0]) + (n-n//op[0]*op[0])*d, 
                helper(-(-n//op[0])) + ((-(-n//op[0]))*op[0]-n)*d) for op in ops)
        m = min(n*d, m)
        dp[n] = m
        return m
        
    return helper(n)

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

Solution (Python):
import heapq
def main():
    T = int(input())
    ans = [None]*T
    ipt = [list(map(int, input().split())) for _ in range(T)]
    for i in range(T):
        n, a, b, c, d = ipt[i]
        dic = {}
        dic[n] = 0
        hq = [-n]
        heapq.heapify(hq)
        while len(hq) > 0:
            p = heapq.heappop(hq)
            p *= -1
            for x in range(p-5, p+6):
                if x <= 1:
                    continue
                if x%2 == 0:
                    if not x//2 in dic:
                        dic[x//2] = float("inf")
                        heapq.heappush(hq, -1*(x//2))
                    if dic[p]+d*abs(x-p)+a < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(x-p)+a
                    if dic[p]+d*abs(p-x//2) < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(p-x//2)
                if x%3 == 0:
                    if not x//3 in dic:
                        dic[x//3] = float("inf")
                        heapq.heappush(hq, -1*(x//3))
                    if dic[p]+d*abs(x-p)+b < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(x-p)+b
                    if dic[p]+d*abs(p-x//3) < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(p-x//3)
                if x%5 == 0:
                    if not x//5 in dic:
                        dic[x//5] = float("inf")
                        heapq.heappush(hq, -1*(x//5))
                    if dic[p]+d*abs(x-p)+c < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(x-p)+c
                    if dic[p]+d*abs(p-x//5) < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(p-x//5)
        ans[i] = min(n*d, dic[1]+d)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil,floor,log

from heapq import *
import sys
input=sys.stdin.readline
T=int(input())
cases=[list(map(int,input().split())) for _ in range(T)]

num=0
cnt=0
def main():
    for i in cases:
        l2=[0]*3
        N,l2[0],l2[1],l2[2],D=i
        d = {}
        num=0
        cnt=0
        for j in range(60):         
            for k in range(38):     
                for l in range(26): 
                    div=pow(2,j)*pow(3,k)*pow(5,l)
                    x=N//div
                    
                    if N%div!=0:
                        c=x+1
                    else:
                        c=x
                    f=x
                    if d.get(c)==None:
                        d[c]=float("inf")
                    if d.get(f)==None:
                        d[f]=float("inf")
        d[N]=0
        
        q=[]
        q.append((0,N))
        heapify(q)
        
        while True:
            dist,u=heappop(q)
            if d[u]<dist: continue
            if u==0:
                print(dist)
                break
            for j in range(3):
                num=1+pow(2,j)
                cnt=l2[j]
                x =u//num
                if u%num!=0:
                    v1 = x+1
                else:
                    v1 = x
                v2 = x
                
                
                alt1 = d[u] + min(cnt+((num-(u%num))%num)*D,(u-v1)*D)
                alt2 = d[u] + min(cnt+(u%num)*D,(u-v2)*D)
                if d[v1] > alt1:
                    d[v1] = alt1
                    heappush(q, (alt1, v1))
                if d[v2] > alt2:
                    d[v2] = alt2
                    heappush(q, (alt2, v2))
            
            
        
        
if __name__ == '__main__':
    main()

Solution (Python):





memo = {}
INF = 10 ** 18

t = int(input())

a = 0
b = 0
c = 0
d = 0

def solve(n):
  global memo, a, b, c, d
  
  if n == 0:
    return 0
  if n in memo:
    return memo[n]
  ans = INF
  
  
  
  if n <= (INF/d):
    ans = n * d
  
  
  for p in range(-1, 2):
    
    x = n + p
    if x < 0 or x % 2 != 0:
      continue
    
    y = x // 2
    if y < n:
      ans = min(ans, a + (abs(p) * d) + solve(y))
  
  
  for p in range(-2, 3):
    x = n + p
    if x < 0 or x % 3 != 0:
      continue
    y = x // 3
    if y < n:
      ans = min(ans, b + (abs(p) * d) + solve(y))
  
  
  for p in range(-4, 5):
    x = n + p
    if x < 0 or x % 5 != 0:
      continue
    y = x // 5
    if y < n:
      ans = min(ans, c + (abs(p) * d) + solve(y))
  
  memo[n] = ans
  return ans
    

def test():
  
  global memo, a, b, c, d
  n, a, b, c, d = map(int, input().split())
  
  memo = {}
  
  
  print(solve(n))

for i in range(t):
  test()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush

sys.setrecursionlimit(10**7)






def run():
    T = int(input())
    for ii in range(T):
        N, A, B, C, D = map(int, input().split())
        stack = [(0, N)]
        min_num = float('inf')
        visited = {}
        while stack:
            money, current = heappop(stack)
            if current > N:continue
            if current in visited.keys():
                continue
            visited[current] = 0
            if current == 0:break

            for pro, cost in ((2, A), (3, B), (5, C)):
                tmp = current % pro
                next_num1 = (current - tmp)//pro
                next_num2 = (current + pro - tmp)//pro
                cond1 = N >= current + pro - tmp
                if pro == 2:
                    heappush(stack, (min(cost, D * next_num1) + tmp * D + money, next_num1))
                    if next_num2 != tmp:
                        heappush(stack, (min((2 - tmp) * D + cost + money, (next_num2 - tmp) * D + money), next_num2))
                elif pro == 3:
                    heappush(stack, (min(cost, D * (2 * next_num1))+ tmp * D + money, next_num1))
                    
                    heappush(stack, (min((3 - tmp) * D + cost + money, (2 * next_num2 - 3 + tmp) * D + money), next_num2))
                else:
                    heappush(stack, (min(cost, D * (4 * next_num1))+ tmp * D + money, next_num1))
                    
                    heappush(stack, (min((5 - tmp) * D + cost + money, (4 * next_num2 - 5 + tmp) * D + money), next_num2))

                
                
                
                
        print(money)
if __name__ == "__main__":
    run()

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

def dfs(n):
  if n in dic:
    return dic[n]
  ret=n*d
  if n%2==0:
    ret=min(ret,a+dfs(n//2))
  elif n%2==1:
    ret=min(ret,a+d+dfs((n-1)//2))
    ret=min(ret,a+d+dfs((n+1)//2))
  if n%3==0:
    ret=min(ret,b+dfs(n//3))
  elif n%3==1:
    ret=min(ret,b+d+dfs((n-1)//3))
    ret=min(ret,b+2*d+dfs((n+2)//3))
  elif n%3==2:
    ret=min(ret,b+2*d+dfs((n-2)//3))
    ret=min(ret,b+d+dfs((n+1)//3))
  if n%5==0:
    ret=min(ret,c+dfs(n//5))
  elif n%5==1:
    ret=min(ret,c+d+dfs((n-1)//5))
    ret=min(ret,c+4*d+dfs((n+4)//5))
  elif n%5==2:
    ret=min(ret,c+2*d+dfs((n-2)//5))
    ret=min(ret,c+3*d+dfs((n+3)//5))
  elif n%5==3:
    ret=min(ret,c+3*d+dfs((n-3)//5))
    ret=min(ret,c+2*d+dfs((n+2)//5))
  elif n%5==4:
    ret=min(ret,c+4*d+dfs((n-4)//5))
    ret=min(ret,c+d+dfs((n+1)//5))
  dic[n]=ret
  return ret

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    T=int(input())         
    for _ in range(T):
        N,A,B,C,D=map(int,input().split())
        memo={}
        def saiki(m):
            if m in memo:
                return memo[m]
            if m==0:
                tmp=0
            elif m==1:
                tmp=D
            else:
                tmp=INF
                for k,P in [(2,A),(3,B),(5,C)]:
                    tmp=min(tmp,saiki(m//k)+(m-m//k*k)*D+min((m//k*k-m//k)*D,P))
                    tmp=min(tmp,saiki(-(-m//k))+(-(-m//k)*k-m)*D+min(((-(-m//k))*k+(-m//k))*D,P))
            memo[m]=tmp
            return tmp
        print(saiki(N))

if __name__ == '__main__':
    main()

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

def solve(n,a,b,c,d):
  mem = {0:0,1:d}
  def f(n):
    if n in mem:
      return mem[n]
    ret = n*d
    if n%2 == 0:
      ret = min(ret,a+f(n//2))
    else:
      ret = min(ret,a+d+f(n//2+1),a+d+f(n//2))
    
    if n%3 == 0:
      ret = min(ret,b+f(n//3))
    elif n%3 == 1:
      ret = min(ret,b+d+f(n//3))
    else:
      ret = min(ret,b+d+f(n//3+1))
    
    if n%5 == 0:
      ret = min(ret,c+f(n//5))
    elif n%5 == 1:
      ret = min(ret,c+d+f(n//5))
    elif n%5 == 2:
      ret = min(ret,c+d+d+f(n//5))
    elif n%5 == 3:
      ret = min(ret,c+d+d+f(n//5+1))
    else:
      ret = min(ret,c+d+f(n//5+1))
    mem[n] = ret
    return ret
  return f(n)
 
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  print(solve(n,a,b,c,d))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def main():
    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:return memo[n]

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

            memo[n] = ret
            return ret
        print(f(N))
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def main():
    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:return memo[n]

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

            memo[n] = ret
            return ret
        print(f(N))
if __name__ == "__main__":
    main()

Solution (Python):
def dist(n):
  if n==0:
    return 0
  if n==1:
    return d
  if n in memo:
    return memo[n]
  
  res=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]=res
  return res

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

Solution (Python):
from heapq import heappop,heappush
from collections import defaultdict
t = int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  q=[(0,n)]
  memo = defaultdict(int)
  while q:
    s,p = heappop(q)
    if memo[p]:
      continue
    memo[p] = 1
    if p == 0:
      print(s)
      break
    heappush(q,(s+d*p,0))
    if p & 1:
      heappush(q,(s+d+a, p//2))
      heappush(q,(s+d+a, p//2+1))
    else:
      heappush(q,(s+a, p//2))
    if p % 3:
      heappush(q,(s+d*(p%3)+b, p//3))
      heappush(q,(s+d*(-p%3)+b, p//3+1))
    else:
      heappush(q,(s+b, p//3))
    if p % 5:
      heappush(q,(s+d*(p%5)+c, p//5))
      heappush(q,(s+d*(-p%5)+c, p//5+1))
    else:
      heappush(q,(s+c, p//5))

Solution (Python):


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

from heapq import heappush, heappop

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

    dq = []

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

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

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

        if cost >= ans:
            continue

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

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

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

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

    return ans


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


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

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

if __name__ == "__main__":
    resolve()

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

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))


t=n_in()


def execute(n, memo, setting):
    if n in memo:
        return memo[n]

    res = setting[1]*n
    for k in [2,3,5]:
        if n%k == 0:
            res = min(res, execute(n//k, memo, setting) + setting[k])
        else:            
            down = (n//k)*k
            res = min(res, execute(down//k, memo, setting) + setting[k] + (n-down)*setting[1])
            up = (n//k)*k+k
            res = min(res, execute(up//k, memo, setting) + setting[k] + (up-n)*setting[1])

    memo[n] = res
    return res

    

for _ in range(t):
    n,a,b,c,d = l_in()

    setting={2: a, 3: b, 5: c, 1: d}
    memo={1: d, 0: 0}

    print(execute(n,memo,setting))

Solution (Python):
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:
      return memo[n]

    m2 = n % 2
    m3 = n % 3
    m5 = n % 5 
    ret = min(
      d * n,
      d * m2 + a + f((n - m2) // 2),
      d * m2 + a + f((n + m2) // 2),
      d * m3 + b + f((n - m3) // 3),
      d * (3 - m3) + b + f((n + 3 - m3) // 3),
      d * m5 + c + f((n - m5) // 5),
      d * (5 - m5) + c + f((n + 5 - m5) // 5),
    )
    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 = [(3, B), (5, C), (2, A)]
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

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

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

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

        if cost >= ans:
            continue

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

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

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

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

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


    return ans


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


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

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

if __name__ == "__main__":
    resolve()

Solution (Python):
t=int(input())
from functools import lru_cache
@lru_cache(maxsize=10000)
def f(x,a,b,c,d):
    if x==1:
        return d
    
    if x==0:
        return 0
    
    res1,res2=0,0
    if x%2:
        res1 = f(x//2,a,b,c,d)+a+d
        res2 = f(x//2+1,a,b,c,d)+a+d
    else:
        res1=res2=f(x//2,a,b,c,d)+a
    res3,res4=0,0
    if x%3:
        res3 = f(x//3,a,b,c,d)+b+d*(x%3)
        res4 = f(x//3+1,a,b,c,d)+b+d*(3-x%3)
    else:
        res3=res4=f(x//3,a,b,c,d)+b
    if x%5:
        res5 = f(x//5,a,b,c,d)+c+d*(x%5)
        res6 = f(x//5+1,a,b,c,d)+c+d*(5-x%5)
    else:
        res5=res6=f(x//5,a,b,c,d)+c
    return(min(res1,res2,res3,res4,res5,res6,x*d))
for _ in range(t):
    n,a,b,c,d=map(int, input().split( ))
    
    ans=f(n,a,b,c,d)
    print(ans)

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

for i 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:
             return memo[n]

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

         memo[n] = ret
         return ret

    print(f(N))

Solution (Python):


N = 0
A = 0
B = 0
C = 0
D = 0
cost_result = {} 
each_cost = {} 

def cost(target):
    """
    Args:
        target: 目標とする数字

    Returns:
        result: その数字に達するまでに必要なコスト
    """
    if target in cost_result:
        return cost_result[target]

    else:
        result_dict = {}
        for i in [2, 3, 5]:
            if target % i == 0:
                result_dict[i] = cost(target//i) + each_cost[i]
            else:
                result_dict[i] = min(
                    cost(target//i) + each_cost[i] + D * (target % i),
                    cost((target//i)+1) + each_cost[i] + D * (i - target % i)
                )
        simplest = target * D
        result = min(min(result_dict.values()), simplest)
        cost_result[target] = result
        return result



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

        each_cost[2] = A
        each_cost[3] = B
        each_cost[5] = C
        cost_result[1] = D
        cost_result = {0:0, 1:D}

        print(cost(N))

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

def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc((x + i) // div) + cost + (sign * x) % div * d for i, sign in [(0, 1), (div - 1, -1)]]
        dp[x] = min(*[value for div, cost in zip(divs, costs) for value in values(div, cost)], x * d)
    return dp[x]

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

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

def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc(x // div) + cost + x % div * d, calc((x + div - 1) // div) + cost + (-x) % div * d]
        dp[x] = min(x * d, *[value for div, cost in zip(divs, costs) for value in values(div, cost)])
    return dp[x]

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    dp = {0: 0, 1: d}
    print(calc(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):
import sys
from functools import lru_cache
t=int(input())
def solve(n,A,B,C,D):
	@lru_cache(None)
	def f(x):
		if x<=1:
			return D*x
		ret=D*x

		if x%2==0:
			ret=min(ret,f(x//2)+A)
		else:
			ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
		
		if x%3==0:
			ret=min(ret,f(x//3)+B)
		elif x%3==1:
			ret=min(ret,f(x//3)+B+D)
		else:
			ret=min(ret,f(x//3+1)+B+D)

		if x%5<=2:
			ret=min(ret,f(x//5)+C+D*(x%5))
		else:
			ret=min(ret,f(x//5+1)+C+D*(5-x%5))
		return ret
	return f(n)
for _ in range(t):
	n,A,B,C,D=map(int,input().split())
	print(solve(n,A,B,C,D))

Solution (Python):
from functools import lru_cache
import sys
def input():
    return sys.stdin.readline()[:-1]

def solve(N, A, B, C, D):
    @lru_cache(None)
    def f(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        
        ret = D * N

        q, r = divmod(N, 2)
        if r == 0:
            
            ret = min(ret, f(q) + A)
        else:
            
            ret = min(ret, f(q) + A + D, f(q+1) + A + D)

        q, r = divmod(N, 3)
        if r == 0:
            
            ret = min(ret, f(q) + B)
        elif r == 1:
            
            ret = min(ret, f(q) + B + D)
        else:
            
            ret = min(ret, f(q+1) + B + D)

        q, r = divmod(N, 5)
        if r == 0:
            
            ret = min(ret, f(q) + C)
        elif r == 1:
            
            ret = min(ret, f(q) + C + D)
        elif r == 2:
            
            ret = min(ret, f(q) + C + D + D)
        elif r == 3:
            
            ret = min(ret, f(q+1) + C + D + D)
        else:
            
            ret = min(ret, f(q+1) + C + D)
        return ret
    return f(N)

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

Solution (Python):
def dfs(n):
    global b,check,d
    
    
    for ttf,cha in zip([2,3,5],b):
        
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
        
        
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Solution (Python):


def main():
    from collections import defaultdict, deque

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

        inf = N * D + 1

        dq = deque()
        dq.append((0, N))  

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

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

            
            ans = min(ans, cost + x * D)

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

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

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
memo=dict()
t=int(input())
def f(x):
	if x in memo:
		return memo[x]
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3+1)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5+1)+C+D*(5-x%5))
	memo[x]=ret
	return ret
for _ in range(t):
	memo=dict()
	n,A,B,C,D=map(int,input().split())
	print(f(n))