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


def main():
    from collections import defaultdict, deque

    inf = 10 ** 27

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

        dq = deque()
        dq.append((0, N))  
        checked = defaultdict(lambda: inf)

        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost >= checked[x]: continue
            checked[x] = cost

            
            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:
                    dq.append((ncost, nx))
                ncost = cost + (d - r) * D + c
                if (r > 0) and (checked[nx + 1] > ncost):
                    dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

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


t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {}
    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 dfs(n):
    global b,check,d
    
    for ttf,cha in zip([2,3,5],b):
        
        check[0]=min(check[n]+n*d,check[0])

        
        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):
check=dict()


def dfs_sub(n,ttf,cha):
    global check,d

    
    check[0]=min(check[n]+n*d,check[0])

    
    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)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

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):
check=dict()
N,z,d=0,[],0


def dfs_sub(n,ttf,cha,d):
    global check

    
    check[0]=min(check[n]+n*d,check[0])

    
    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)


def dfs(n):
    global b,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j,d)

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

Solution (Python):
def solve(N, A, B, C, D):
    d = {0:0, 1:D}
    s = set()
    return dfs(N, A, B, C, D, d, s)

def dfs(n, A, B, C, D, d, s):
    if n in d:
        return d[n]
    if n in s:
        return float('inf')
    
    s.add(n)
    ans = float('inf')
    
    p = n % 2
    if p == 0:
        ans = min(ans, dfs(n // 2, A, B, C, D, d, s) + A)
    else:
        ans = min(ans, dfs((n - p) // 2, A, B, C, D, d, s) + A + D * p)
        ans = min(ans, dfs((n + (2 - p)) // 2, A, B, C, D, d, s) + A + D * (2 - p))

    q = n % 3
    if q == 0:
        ans = min(ans, dfs(n // 3, A, B, C, D, d, s) + B)
    else:
        ans = min(ans, dfs((n - q) // 3, A, B, C, D, d, s) + B + D * q)
        ans = min(ans, dfs((n + (3 - q)) // 3, A, B, C, D, d, s) + B + D * (3 - q))
    
    r = n % 5
    if r == 0:
        ans = min(ans, dfs(n // 5, A, B, C, D, d, s) + C)
    else:
        ans = min(ans, dfs((n - r) // 5, A, B, C, D, d, s) + C + D * r)
        ans = min(ans, dfs((n + (5 - r)) // 5, A, B, C, D, d, s) + C + D * (5 - r))
    
    ans = min(ans, D * n)
    
    d[n] = ans
    return ans

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)

Solution (Python):
check=dict()
N,z,d=0,[],0


def dfs_sub(n,ttf,cha):
    global check,d

    
    check[0]=min(check[n]+n*d,check[0])

    
    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)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

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

Solution (Python):
check=dict()
N,z,d=0,[],0


def dfs_sub(n,ttf,cha):
    global check,d

    
    check[0]=min(check[n]+n*d,check[0])

    
    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)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

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

Solution (Python):
check=dict()
N,z,d=0,[],0


def dfs_sub(n,ttf,cha):
    global check,d

    
    check[0]=min(check[n]+n*d,check[0])

    
    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)


def dfs(n):
    global z
    for i,j in z:
        dfs_sub(n,i,j)

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

Solution (Python):
check=dict()
N,b,d=0,[],0


def dfs_sub(n,ttf,cha):
    global check,d

    
    check[0]=min(check[n]+n*d,check[0])

    
    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)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

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):
check=dict()
N,b,d=0,[],0


def dfs_sub(n,ttf,cha):
    global check,d
    
    check[0]=min(check[n]+n*d,check[0])

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


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

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):
import sys
sys.setrecursionlimit(10**7)
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    def dfs(x):
        if x==0:
            return 0
        if x==1:
            return d
        if x in memo:
            return memo[x]
        l2=2*(x//2)
        r2=2*(-(-x//2))
        l3=3*(x//3)
        r3=3*(-(-x//3))
        l5=5*(x//5)
        r5=5*(-(-x//5))
        mini=d*x
        mini=min(mini,abs(l2-x)*d+a+dfs(l2//2))
        mini=min(mini,abs(r2-x)*d+a+dfs(r2//2))
        mini=min(mini,abs(l3-x)*d+b+dfs(l3//3))
        mini=min(mini,abs(r3-x)*d+b+dfs(r3//3))
        mini=min(mini,abs(l5-x)*d+c+dfs(l5//5))
        mini=min(mini,abs(r5-x)*d+c+dfs(r5//5))
        memo[x]=mini
        return mini
    print(dfs(n))

Solution (Python):
import heapq

def pay2win():
  num = set()
  q = []
  heapq.heapify(q)
  heapq.heappush(q,( 0, N ))
  cost = N*D
  while q:
    c0, n0 = heapq.heappop(q)
    if n0 in num:
      continue
    num.add(n0)
    if n0 == 0:
      break
    if c0 >= cost:
      break
    cost = min(cost,c0+n0*D)
    
    n2, m = divmod(n0, 2)
    if m == 0:
      heapq.heappush(q,( c0+A, n2 ))
    else:
      heapq.heappush(q,( c0+D+A, n2 ))
      heapq.heappush(q,( c0+D+A, n2+1 ))
    
    n3, m = divmod(n0, 3)
    if m == 0:
      heapq.heappush(q,( c0+B, n3 ))
    elif m == 1:
      heapq.heappush(q,( c0+D+B, n3 ))
    else:
      heapq.heappush(q,( c0+D+B, n3+1 ))
    
    n5, m = divmod(n0, 5)
    if m == 0:
      heapq.heappush(q,( c0+C, n5 ))
    elif m <= 2:
      heapq.heappush(q,( c0+D*m+C, n5 ))
    else:
      heapq.heappush(q,( c0+D*(5-m)+C, n5+1 ))
    
  print(cost)


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

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    import heapq
    from collections import defaultdict
    inf=10**18+1
    for _ in range(T):
        
        L=[0]*4
        N,L[0],L[1],L[2],L[3]=MI()
        LL=[2,3,5]
        dd = defaultdict(lambda: inf)
        dd[0]=0
        q=[(0,N,1)]
        heapq.heapify(q)
        ans=L[3]*N
        while True:
            cost,now,flag=heapq.heappop(q)
            if now==0:
                ans=cost
                break
            if cost>ans:
                break
            ans=min(ans,cost+now*L[3])
            
            for i in range(3):
                if now%LL[i]==0:
                    nxt=now//LL[i]
                    ncost=cost+L[i]
                    if ncost<dd[nxt]:
                        dd[nxt]=ncost
                        heapq.heappush(q,(ncost,nxt,1))
            
            if flag:
                for k in range(1,5):
                    for pm in [1,-1]:
                        nxt=now+k*pm
                        ncost=cost+L[3]*k
                        if ncost<dd[nxt]:
                            dd[nxt]=ncost
                            heapq.heappush(q,(ncost,nxt,0))
                    
        print(ans)
                
                    
            
        
        
        
        
        
        

main()

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):
from functools import lru_cache

def calc(n):
    @lru_cache(maxsize=None)
    def rec(n):
        if n <= 0: return 0
        S = [2, 3, 5]
        mi = D * n
        for i, a in enumerate(S):
            for j in range(-a//2, a//2 + 1):
                if (n + j) % a == 0 and (n + j) // a < n:
                    mi = min(mi, rec((n+j) // a) + X[i] + D * abs(j))
        return mi
    return rec(n)

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

Solution (Python):
from functools import lru_cache

def solve(n,a,b,c,d):
    @lru_cache(None)
    def rec(cur):
        if cur == 0:    return 0
        if cur == 1:    return d
        ret = cur * d
        p,q = divmod(cur, 2)
        if q == 0:  ret = min(ret, rec(p) + a)
        if q == 1:  ret = min(ret, rec(p) + a + d, rec(p + 1) + a + d)
        p,q = divmod(cur, 3)
        if q == 0:  ret = min(ret, rec(p) + b)
        if q == 1:  ret = min(ret, rec(p) + b + d)
        if q == 2:  ret = min(ret, rec(p) + b + d * 2, rec(p + 1) + b + d)
        p,q = divmod(cur, 5)
        if q == 0:  ret = min(ret, rec(p) + c)
        if q == 1:  ret = min(ret, rec(p) + c + d)
        if q == 2:  ret = min(ret, rec(p) + c + d * 2)
        if q == 3:  ret = min(ret, rec(p) + c + d * 3, rec(p + 1) + c + d * 2)
        if q == 4:  ret = min(ret, rec(p) + c + d * 4, rec(p + 1) + c + d)
        return ret

    return rec(n)

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

Solution (Python):
import sys 
sys.setrecursionlimit(10**6)
from collections import defaultdict
t = int(input())


def solve():
    n,a,b,c,d = map(int, input().split())
    memo = defaultdict(int)
    def f(n):
        if memo[n] != 0:
            return memo[n]
        if n == 2:
            return min(a+d,2*d)
        if n == 1:
            return d 
        if n == 0:
            return 0 
        
        r2 = n % 2
        n_p_2 = n + 2 - r2
        n_m_2 = n - r2
        d_p_2 = f(n_p_2//2) + d*(2-r2) + a
        d_m_2 = f(n_m_2//2) + d*(r2) + a
        r3 = n % 3
        n_p_3 = n + 3 - r3
        n_m_3 = n - r3
        d_p_3 = f(n_p_3//3) + d*(3-r3) + b
        d_m_3 = f(n_m_3//3) + d*(r3) + b
        r5 = n % 5
        n_p_5 = n + 5 - r5
        n_m_5 = n - r5
        d_p_5 = f(n_p_5//5) + d*(5-r5) + c
        d_m_5 = f(n_m_5//5) + d*(r5) + c
        ret = min(n*d,d_p_2,d_p_3,d_p_5,d_m_2,d_m_3,d_m_5)
        memo[n] = ret
        return ret
    ans = f(n)
    return ans
     

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

for a in ans:
    print(a)

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

T = int(input())

memo = {}
def solve(n, a, b, c, d):
  global memo
  if n in memo:
    return memo[n]
  res = []
  flag = [True] * 6
  for i in range(5):
    n1 = n - i; n2 = n + i
    if n1:
      if n1 % 2 == 0 and flag[0]:
        flag[0] = False
        v = solve(n1//2, a, b, c, d) + min(a + i*d, (n1//2 + i)*d)
        res.append(v)
      if n1 % 3 == 0 and flag[2]:
        flag[2] = False
        v = solve(n1//3, a, b, c, d) + min(b + i*d, (2*n1//3 + i)*d)
        res.append(v)
      if n1 % 5 == 0 and flag[4]:
        flag[4] = False
        v = solve(n1//5, a, b, c, d) + min(c + i*d, (4*n1//5 + i)*d)
        res.append(v)
    if n2 % 2 == 0 and flag[1]:
      flag[1] = False
      v = solve(n2//2, a, b, c, d) + min(a + i*d, abs(n-n2//2)*d)
      res.append(v)
    if n2 % 3 == 0 and flag[3]:
      flag[3] = False
      v = solve(n2//3, a, b, c, d) + min(b + i*d, abs(n-n2//3)*d)
      res.append(v)
    if n2 % 5 == 0 and flag[5]:
      flag[5] = False
      v = solve(n2//5, a, b, c, d) + min(c + i*d, abs(n-n2//5)*d)
      res.append(v)
  v = min(res)
  memo[n] = v
  return v


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

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

Solution (Python):

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

    def dfs(n):
        if n in memo.keys():
            return memo[n]

        res1 = n*d
        r = n % 2
        res2 = a+r*d+dfs((n-r)//2)
        if r != 0:
            tmp = a+(2-r)*d+dfs((n+(2-r))//2)
            if tmp < res2:
                res2 = tmp

        r = n % 3
        res3 = b+r*d+dfs((n-r)//3)
        if r != 0:
            tmp = b+(3-r)*d+dfs((n+(3-r))//3)
            if tmp < res3:
                res3 = tmp

        r = n % 5
        res5 = c+r*d+dfs((n-r)//5)
        if r != 0:
            tmp = c+(5-r)*d+dfs((n+(5-r))//5)
            if tmp < res5:
                res5 = tmp

        memo[n] = min(res1, res2, res3, res5)
        return memo[n]

    print(dfs(n))

Solution (Python):

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

    def dfs(n):
        if n in memo.keys():
            return memo[n]

        res1 = n*d
        r = n % 2
        res2 = a+r*d+dfs((n-r)//2)
        if r != 0:
            tmp = a+(2-r)*d+dfs((n+(2-r))//2)
            if tmp < res2:
                res2 = tmp

        r = n % 3
        res3 = b+r*d+dfs((n-r)//3)
        if r != 0:
            tmp = b+(3-r)*d+dfs((n+(3-r))//3)
            if tmp < res3:
                res3 = tmp

        r = n % 5
        res5 = c+r*d+dfs((n-r)//5)
        if r != 0:
            tmp = c+(5-r)*d+dfs((n+(5-r))//5)
            if tmp < res5:
                res5 = tmp

        memo[n] = min(res1, res2, res3, res5)
        return memo[n]

    print(dfs(n))

Solution (Python):
from functools import *
from math import *

t = int(input())

@lru_cache(maxsize=None)
def sol(n, a, b, c, d):
    if n == 1: return d
    ans = n * d
    cn = (n + 1) // 2
    fn = n // 2
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 2 - n) * d + a)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 2 - n) * d + a)
    cn = (n + 2) // 3
    fn = n // 3
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 3 - n) * d + b)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 3 - n) * d + b)
    cn = (n + 4) // 5
    fn = n // 5
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 5 - n) * d + c)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 5 - n) * d + c)
    
    return ans

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    sol.cache_clear()
    print(min(d * n, sol(n, a, b, c, d)))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


t = I()
for _ in range(t):
    n, a, b, c, d = LI()
    D = defaultdict(int)
    def f(x):
        if D[x]:
            return D[x]
        if x == 0:
            return 0
        if x == 1:
            return d
        ret = INF
        ret = min(ret, f(x // 2) + x % 2 * d + a)
        ret = min(ret, f(x // 3) + x % 3 * d + b)
        ret = min(ret, f(x // 5) + x % 5 * d + c)
        if x % 2:
            ret = min(ret, f(x // 2 + 1) + (2 - x % 2) * d + a)
        if x % 3:
            ret = min(ret, f(x // 3 + 1) + (3 - x % 3) * d + b)
        if x % 5:
            ret = min(ret, f(x // 5 + 1) + (5 - x % 5) * d + c)
        ret = min(ret, x * d)
        D[x] = ret
        return ret

    print(f(n))

Solution (Python):
from math import ceil
import sys
sys.setrecursionlimit(10**7)
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    def dfs(x):
        if x==0:
            return 0
        if x==1:
            return d
        if x in memo:
            return memo[x]
        l2=2*(x//2)
        r2=2*((x+1)//2)
        l3=3*(x//3)
        r3=3*((x+2)//3)
        l5=5*(x//5)
        r5=5*((x+4)//5)
        mini=d*x
        mini=min(mini,abs(l2-x)*d+a+dfs(l2//2))
        mini=min(mini,abs(r2-x)*d+a+dfs(r2//2))
        mini=min(mini,abs(l3-x)*d+b+dfs(l3//3))
        mini=min(mini,abs(r3-x)*d+b+dfs(r3//3))
        mini=min(mini,abs(l5-x)*d+c+dfs(l5//5))
        mini=min(mini,abs(r5-x)*d+c+dfs(r5//5))
        memo[x]=mini
        return mini
    print(dfs(n))

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

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

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):
t = int(input())

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


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):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
INF = 10**18
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = defaultdict(lambda: INF)

    def dfs(n, cost):

        if memo[n] <= cost:
            return 0

        memo[n] = cost
        if n == 0:
            return 0

        dfs(0, cost+n*d)

        r = n % 2
        dfs((n-r)//2, cost+a+r*d)
        if r != 0:
            dfs((n+(2-r))//2, cost+a+(2-r)*d)

        r = n % 3
        dfs((n-r)//3, cost+b+r*d)
        if r != 0:
            dfs((n+(3-r))//3, cost+b+(3-r)*d)

        r = n % 5
        dfs((n-r)//5, cost+c+r*d)
        if r != 0:
            dfs((n+(5-r))//5, cost+c+(5-r)*d)
            
    dfs(n, 0)
    print(memo[0])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def solve():
    N,A,B,C,D=map(int,input().split())
    memo={}
    def rec(x):
        if x in memo:
            return memo[x]
        if x==1:
            return D
        if x==0:
            return 0
        res=D*x
        for y,cost in zip([2,3,5],[A,B,C]):
            res=min(res,rec(x//y)+abs(x-(x//y*y))*D+cost)
            res=min(res,rec((x+y-1)//y)+abs(x-(((x+y-1)//y)*y))*D+cost)
            
        memo[x]=res
        return res
    print(rec(N))

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

Solution (Python):
from math import floor,ceil
import sys
sys.setrecursionlimit(10**7)
def solve():
    N,A,B,C,D=map(int,input().split())
    memo={}
    def dist(n):
        if n in memo:
            return memo[n]
        if n==1:
            return D
        if n==0:
            return 0
        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
    print(dist(N))

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

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)
@lru_cache(maxsize=None)
def dfs(N,A,B,C,D):
  ans=N*D
  for x, y in [(2, A), (3, B), (5, C)]:
    if N%x==0:
      N0=N//x
      a=dfs(N0,A,B,C,D)+y
      ans=min(a,ans)
    elif x<=N:
      z=N%x
      N0=(N-z)//x
      N1=(N-z+x)//x
      a=dfs(N0,A,B,C,D)+z*D+y
      b=dfs(N1,A,B,C,D)+((x-z)*D)+y
      ans=min(a,b,ans)
  return ans
T=int(input())
for _ in range(T):
  N,A,B,C,D=map(int,input().split())
  print(dfs(N,A,B,C,D))

Solution (Python):
t=int(input())
from functools import lru_cache
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    @lru_cache(maxsize=100000)
    def f(n):
        if n==0:
            return 0
        if n==1:
            return d
        ans=d*n
        q,r=divmod(n,2)
        if r==0:
            ans=min(ans,f(q)+a+d*r)
        else:
            ans=min(ans,f(q)+a+d*r,f(q+1)+a+d*(2-r))
        q,r=divmod(n,3)
        if r==0:
            ans=min(ans,f(q)+b+d*r)
        else:
            ans=min(ans,f(q)+b+d*r,f(q+1)+b+d*(3-r))
        q,r=divmod(n,5)
        if r==0:
            ans=min(ans,f(q)+c+d*r)
        else:
            ans=min(ans,f(q)+c+d*r,f(q+1)+c+d*(5-r))
        return ans
    print(f(n))

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

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

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 math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


t = I()
for _ in range(t):
    n, a, b, c, d = LI()
    memo = {0: 0, 1: d}
    def dfs(x):
        if x in memo:
            return memo[x]
        ret = x * d
        ret = min(ret, min(dfs(x // 2), dfs((x - 1) // 2 + 1)) + a + d * (x % 2))
        ret = min(ret, min(dfs(x // 3) + b + d * (x % 3), dfs((x - 1) // 3 + 1) + b + d * (-x % 3)))
        ret = min(ret, min(dfs(x // 5) + c + d * (x % 5), dfs((x - 1) // 5 + 1) + c + d * (-x % 5)))
        memo[x] = ret
        return ret

    print(dfs(n))

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 6)

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

    @lru_cache(maxsize=None)
    def rec(n):
        if n == 0:
            return 0

        min_ = n * D
        min_ = min(min_, (n % 2) * D + A + rec(n // 2))
        if n // 2 + 1 != n:
            min_ = min(min_, (2 - n % 2) * D + A + rec(n // 2 + 1))

        min_ = min(min_, (n % 3) * D + B + rec(n // 3))
        if n // 3 + 1 != n:
            min_ = min(min_, (3 - n % 3) * D + B + rec(n // 3 + 1))

        min_ = min(min_, (n % 5) * D  + C + (rec(n // 5)))
        if n // 5 + 1 != n:
            min_ = min(min_, (5 - n % 5) * D + C + rec(n // 5 + 1))

        return min_

    print(rec(N))