Problem:
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.**

Incorrect submission (verdict: Wrong Answer):
def solve(n, a, b, c, d, bi=1):

    curr = n
    coin = d

    while curr != 1:
        ca = curr / 2 / a
        cb = curr * 2 / 3 / b
        cc = curr * 4 / 5 / c
        cd = 1 / d

        cs = [(ca, 2, a), (cb, 3, b), (cc, 5, c), (cd, 1, d)]
        cs.sort(reverse=True)

        if cs[0][1] == 1:
            curr = 1
            coin += (curr - 1) * d
            break

        if curr % 2 != 0 and curr % 3 != 0 and curr % 5 != 0:
            curr += bi
            coin += d
            continue

        if curr % cs[0][1] == 0 and cs[0][1] != 1 and curr >= cs[0][1]:
            curr //= cs[0][1]
            coin += cs[0][2]
            continue

        if curr % cs[1][1] == 0 and cs[1][1] != 1 and curr >= cs[1][1]:
            curr //= cs[1][1]
            coin += cs[1][2]
            continue

        if curr % cs[2][1] == 0 and cs[2][1] != 1 and curr >= cs[2][1]:
            curr //= cs[2][1]
            coin += cs[2][2]
            continue

        if curr % cs[3][1] == 0 and cs[3][1] != 1 and curr >= cs[3][1]:
            curr //= cs[3][1]
            coin += cs[3][2]
            continue

        coin = float("inf")
        break

    return coin


t = int(input())
ans = []
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    ans.append(min(solve(n, a, b, c, d, -1), solve(n, a, b, c, d, 1)))

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

Fixed, accepted submission:
from functools import lru_cache


def solve(n, a, b, c, d):

    @lru_cache(maxsize=None)
    def func(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        else:
            
            coin = d * n

            
            div, mod = divmod(n, 2)

            if mod == 0:
                coin = min(coin, func(div) + a)
            else:
                coin = min(coin, func(div) + a + d, func(div + 1) + a + d)

            
            div, mod = divmod(n, 3)

            if mod == 0:
                coin = min(coin, func(div) + b)
            elif mod == 1:
                coin = min(coin, func(div) + b + d, func(div + 1) + b + 2 * d)
            else:
                coin = min(coin, func(div) + b + 2 * d, func(div + 1) + b + d)

            
            div, mod = divmod(n, 5)

            if mod == 0:
                coin = min(coin, func(div) + c)
            elif mod == 1:
                coin = min(coin, func(div) + c + d, func(div + 1) + c + 4 * d)
            elif mod == 2:
                coin = min(coin, func(div) + c + 2 * d, func(div + 1) + c + 3 * d)
            elif mod == 3:
                coin = min(coin, func(div) + c + 3 * d, func(div + 1) + c + 2 * d)
            else:
                coin = min(coin, func(div) + c + 4 * d, func(div + 1) + c + d)

        return coin
    return func(n)


t = int(input())
ans = []
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    ans.append(solve(n, a, b, c, d))

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