Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.popleft()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

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


Fixed submission:
from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.popleft()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

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

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.pop()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

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


Fixed submission:
from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.popleft()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

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