Buggy python submission (verdict: Runtime Error):
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))


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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = set()
    # (coin, x)
    search = [(d, 1, 0, 0, 0, 0)]
    first = True

    while 1:
        coin, x, add, f2, f3, f5 = heapq.heappop(search)
#         print(f'coin: {coin}, x: {x}, add: {add}, f2: {f2}, f3: {f3}, f5: {f5}')
        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest.add(x)

            if add >=0:
                heapq.heappush(search, (coin + d, x + 1, add + 1, 0, 0, 0))
            if x - 1 > 1 and add <= 0:
                heapq.heappush(search, (coin + d, x - 1, add - 1, 0, 0, 0))
                
            if 2 * x <= 2 * n:
                heapq.heappush(search, (coin + a, 2 * x, 0, f2 + 1, f3, f5))
            if 3 * x <= 2 * n and f2 == 0:
                heapq.heappush(search, (coin + b, 3 * x, 0, f2, f3 + 1, f5))
            if 5 * x <= 2 * n and f2 == 0 and f3 == 0:
                heapq.heappush(search, (coin + c, 5 * x, 0, f2, f3, f5 + 1))
                

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

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = dict()
    # (coin, x)
    search = [(d, 1)]
    first = True

    while 1:
        coin, x = heapq.heappop(search)

        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest[x] = coin

            heapq.heappush(search, (coin + a, 2 * x))
            heapq.heappush(search, (coin + b, 3 * x))
            heapq.heappush(search, (coin + c, 5 * x))
            heapq.heappush(search, (coin + d, x + 1))
            if x - 1 > 1:
                heapq.heappush(search, (coin + d, x - 1))

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

Buggy python submission (verdict: Runtime Error):
import heapq
import numpy as np

t = int(input())

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = dict()
    # (coin, x)
    search = [(d, 1)]
    first = True

    while 1:
        coin, x = heapq.heappop(search)

        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest[x] = coin

            heapq.heappush(search, (coin + a, 2 * x))
            heapq.heappush(search, (coin + b, 3 * x))
            heapq.heappush(search, (coin + c, 5 * x))
            heapq.heappush(search, (coin + d, x + 1))
            if x - 1 > 1:
                heapq.heappush(search, (coin + d, x - 1))

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