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):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product

#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    T = int(input())
    for ii in range(T):
        N, A, B, C, D = map(int, input().split())
        stack = [(0, N)]
        min_num = float('inf')
        visited = {}
        while stack:
            money, current = heappop(stack)
            if current in visited.keys():
                continue
            visited[current] = 0
            if current == 0:break

            for pro, cost in ((2, A), (3, B), (5, C)):
                tmp = current % pro
                next_num1 = (current - tmp)//pro
                next_num2 = (current + pro - tmp)//pro
                if pro == 2:
                    heappush(stack, (min(cost, D * next_num1) + tmp * D + money, next_num1))
                    if next_num2 != tmp and (not next_num2 % 3 or not next_num2 % 5):
                        heappush(stack, (min((2 - tmp) * D + cost + money, (next_num2 - tmp) * D + money), next_num2))
                elif pro == 3:
                    heappush(stack, (min(cost, D * (2 * next_num1))+ tmp * D + money, next_num1))
                    if next_num2 != tmp and (not next_num2 % 2 or not next_num2 % 5):
                        heappush(stack, (min((3 - tmp) * D + cost + money, (2 * next_num2 - tmp) * D + money), next_num2))
                else:
                    heappush(stack, (min(cost, D * (4 * next_num1))+ tmp * D + money, next_num1))
                    if next_num2 != tmp and (not next_num2 % 2 or not next_num2 % 3):
                        heappush(stack, (min((5 - tmp) * D + cost + money, (4 * next_num2 - tmp) * D + money), next_num2))

                #if next_num1 < min_num:
                #    heappush(stack, (min(cost, D * ((pro-1) * next_num1))+ tmp * D + money, next_num1))
                #if next_num2 < min_num and (pro - 1) * next_num2 != tmp and current < 5:
                
        print(money)
if __name__ == "__main__":
    run()


Fixed, accepted submission:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product

#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    T = int(input())
    for ii in range(T):
        N, A, B, C, D = map(int, input().split())
        stack = [(0, N)]
        min_num = float('inf')
        visited = {}
        while stack:
            money, current = heappop(stack)
            if current > N:continue
            if current in visited.keys():
                continue
            visited[current] = 0
            if current == 0:break

            for pro, cost in ((2, A), (3, B), (5, C)):
                tmp = current % pro
                next_num1 = (current - tmp)//pro
                next_num2 = (current + pro - tmp)//pro
                cond1 = N >= current + pro - tmp
                if pro == 2:
                    heappush(stack, (min(cost, D * next_num1) + tmp * D + money, next_num1))
                    if next_num2 != tmp:# and (not next_num2 % 3 or not next_num2 % 5):
                        heappush(stack, (min((2 - tmp) * D + cost + money, (next_num2 - tmp) * D + money), next_num2))
                elif pro == 3:
                    heappush(stack, (min(cost, D * (2 * next_num1))+ tmp * D + money, next_num1))
                    #if 2 * next_num2 != tmp:# and (not next_num2 % 2 or not next_num2 % 5):
                    heappush(stack, (min((3 - tmp) * D + cost + money, (2 * next_num2 - 3 + tmp) * D + money), next_num2))
                else:
                    heappush(stack, (min(cost, D * (4 * next_num1))+ tmp * D + money, next_num1))
                    #if 4 * next_num2 != tmp:# and (not next_num2 % 2 or not next_num2 % 3):
                    heappush(stack, (min((5 - tmp) * D + cost + money, (4 * next_num2 - 5 + tmp) * D + money), next_num2))

                #if next_num1 < min_num:
                #    heappush(stack, (min(cost, D * ((pro-1) * next_num1))+ tmp * D + money, next_num1))
                #if next_num2 < min_num and (pro - 1) * next_num2 != tmp and current < 5:
                
        print(money)
if __name__ == "__main__":
    run()