Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    ch1 = [[[N]*100 for _ in range(100)] for __ in range(100)]
    ch2 = [[[N]*100 for _ in range(100)] for __ in range(100)]
    ch1[0][0][0] = 0
    ch2[0][0][0] = 0
    deq = deque([[N,0,0,0,0]])
    MIN = INF
    while len(deq) != 0:
        n,a,b,c,d = deq.popleft()
        am = n % 2
        n2 = n // 2
        MIN = min(MIN,a*A+b*B+c*C+D*(d+n-1))
        if n2 == 0:
            continue
        if n2 == 1:
            MIN = min(MIN,(a+1)*A+b*B+c*C+D*(d+am))
        else:
            if ch1[a+1][b][c] > d+am:
                ch1[a+1][b][c] = d+am
                deq.append([n2,a+1,b,c,d+am])
            if ch2[a+1][b][c] > d+1:
                ch2[a+1][b][c] = d+1
                deq.append([n2+1,a+1,b,c,d+1])
        bm = n % 3
        n3 = n // 3
        if n3 == 0:
            continue
        if n3 == 1:
            MIN = min(MIN,a*A+(b+1)*B+c*C+D*(d+bm))
        else:
            if ch1[a][b+1][c] > d+bm:
                ch1[a][b+1][c] = d+bm
                deq.append([n3,a,b+1,c,d+bm])
            if ch2[a][b+1][c] > d+1+bm%2:
                ch2[a][b+1][c] = d+1+bm%2
                deq.append([n3+1,a,b+1,c,d+1+bm%2])
        cm = n % 5
        n5 = n // 5
        if n5 == 0:
            continue
        if n5 == 1:
            if cm == 4:
                cmm = 2
            else:
                cmm = cm
            MIN = min(MIN,a*A+b*B+(c+1)*C+D*(d+cmm))
        else:
            if cm <= 2:
                if ch1[a][b][c+1] > d+cm:
                    ch1[a][b][c+1] = d+cm
                    deq.append([n5,a,b,c+1,d+cm])
                if ch2[a][b][c+1] > d+cm+1:
                    ch2[a][b][c+1] = d+cm+1
                    deq.append([n5,a,b,c+1,d+cm+1])
            else:
                if ch1[a][b][c+1] > d+6-cm:
                    ch1[a][b][c+1] = d+6-cm
                    deq.append([n5,a,b,c+1,d+6-cm])
                if ch2[a][b][c+1] > d+5-cm:
                    ch2[a][b][c+1] = d+5-cm
                    deq.append([n5,a,b,c+1,d+5-cm])
    print(MIN+D)

Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
t = int(input())
for _ in range(t):
    n, a, b, c, da = map(int, input().split())
    hq = [(0, n)]
    d = defaultdict(lambda: 10 ** 25)
    d[n] = 0
    while hq:
        cs, p = heapq.heappop(hq)
        if d[p] < cs:
            continue
        if d[p // 2] > cs + a + (p % 2) * da:
            heapq.heappush(hq, (cs + a + (p % 2) * da, p // 2))
            d[p // 2] = cs + a + (p % 2) * da
        if d[p // 2 + 1] > cs + a + da:
            heapq.heappush(hq, (cs + a + da, p // 2 + 1))
            d[p // 2 + 1] = cs + a + da
        if d[p // 3] > cs + b + (p % 3) * da:
            heapq.heappush(hq, (cs + b + (p % 3) * da, p // 3))
            d[p // 3] = cs + b + (p %3) * da
        if d[p // 3 + 1] > cs + b +  (1+(p%3)%2)* da:
            heapq.heappush(hq, (cs + b + (1+(p%3)%2) * da, p // 3 + 1))
            d[p // 3 + 1] = cs + b + (1+(p%3)%2) * da
        ccc = p % 5
        if ccc <= 2:
            if d[p//5] > cs+c+ccc*da:
                heapq.heappush(hq,(cs+c+ccc*da,p//5))
                d[p//5] = cs+c+ccc*da
            if d[p//5 +1] > cs+c+(ccc+1)*da:
                heapq.heappush(hq,(cs+c+(ccc+1)*da,p//5 +1))
                d[p//5 +1] = cs+c+(ccc+1)*da
        else:
            if d[p//5] > cs+c+(6-ccc)*da:
                heapq.heappush(hq,(cs+c+(6-ccc)*da,p//5))
                d[p//5] = cs+c+(6-ccc)*da
            if d[p//5 +1] > cs+c+(5-ccc)*da:
                heapq.heappush(hq,(cs+c+(5-ccc)*da,p//5 +1))
                d[p//5 +1] = cs+c+(5-ccc)*da
    ans = 10 ** 25
    for k, v in d.items():
        ans = min(ans, k * da + v)
    print(ans)