Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if dp[rem] <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = sorted([(a, 2), (b, 3), (c, 5)],
                     key=lambda x: x[1]//x[0], reverse=True)
        ans = n*d
        stack = [(n, d)]  # remaining, cost
        while stack:
            rem, cost = stack.pop()
            if rem <= 1:
                ans = min(ans, cost)
                continue
            for y, x in ABC:
                if cost+y < ans:
                    stack.append((rem//x, (rem % x)*d+cost+y))
                    stack.append((-(-rem//x), (-rem % x)*d+cost+y))

        ret.append(str(ans))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Fixed submission:
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))