Buggy python submission (verdict: Time Limit Exceeded):
import math

def cost_compare(v,w,L,K,Z):
    if w in L:
        return min(K[v]+Z,K[w])
    elif w in K:
        return K[w]
    else:
        return K[v]+Z

T=int(input())


f=True
for t in range(T):
    N,A,B,C,D=map(int,input().split())

    K={0:0} #最小のコストの辞書
    L={0:0} #Kのうち未確定のものへの制限

    g=0
    while g<=10:
        v=min(L.items(),key=lambda x:x[1])[0]

        del L[v]
        
        m=cost_compare(v,2*v,L,K,A)
        if (2*v in L) or (2*v not in K):
            L[2*v]=m
        K[2*v]=m

        m=cost_compare(v,3*v,L,K,B)
        if (3*v in L) or (3*v not in K):
            L[3*v]=m
        K[3*v]=m

        m=cost_compare(v,5*v,L,K,C)
        if (5*v in L) or (5*v not in K):
            L[5*v]=m
        K[5*v]=m

        m=cost_compare(v,v+1,L,K,D)
        if (v+1 in L) or (v+1 not in K):
            L[v+1]=m
        K[v+1]=m

        if v>=1:
            m=cost_compare(v,v-1,L,K,D)
            if (v-1 in L) or (v-1 not in K):
                L[v-1]=m
            K[v-1]=m

        if v==N:g=1
        if g!=0:
            g+=1
        
    print(K[N])


Fixed submission:
T=int(input())
for i in range(T):
    N,A,B,C,D=map(int,input().split())

    M={0:0,1:D}

    def f(N):
        if N in M:
            return M[N]
        
        p,q=N//2*2,(N+1)//2*2
        r,s=N//3*3,(N+2)//3*3
        t,u=N//5*5,(N+4)//5*5
        R=min(D*N,
              D*abs(N-p)+A+f(p//2),
              D*abs(N-q)+A+f(q//2),
              
              D*abs(N-r)+B+f(r//3),
              D*abs(N-s)+B+f(s//3),
              
              D*abs(N-t)+C+f(t//5),
              D*abs(N-u)+C+f(u//5),
              )

        M[N]=R
        return R
    
    print(f(N))

Buggy python submission (verdict: Time Limit Exceeded):
import math

def cost_compare(v,w,L,K,Z):
    if w in L:
        return min(K[v]+Z,K[w])
    elif w in K:
        return K[w]
    else:
        return K[v]+Z

T=int(input())


f=True
for t in range(T):
    N,A,B,C,D=map(int,input().split())

    K={0:0} #最小のコストの辞書
    L={0:0} #Kのうち未確定のものへの制限

    g=0
    while g<=10:
        v=min(L)

        del L[v]
        
        m=cost_compare(v,2*v,L,K,A)
        if (2*v in L) or (2*v not in K):
            L[2*v]=m
        K[2*v]=m

        m=cost_compare(v,3*v,L,K,B)
        if (3*v in L) or (3*v not in K):
            L[3*v]=m
        K[3*v]=m

        m=cost_compare(v,5*v,L,K,C)
        if (5*v in L) or (5*v not in K):
            L[5*v]=m
        K[5*v]=m

        m=cost_compare(v,v+1,L,K,D)
        if (v+1 in L) or (v+1 not in K):
            L[v+1]=m
        K[v+1]=m

        if v>=1:
            m=cost_compare(v,v-1,L,K,D)
            if (v-1 in L) or (v-1 not in K):
                L[v-1]=m
            K[v-1]=m

        if v==N:g=1
        if g!=0:
            g+=1
        
    print(K[N])


Fixed submission:
T=int(input())
for i in range(T):
    N,A,B,C,D=map(int,input().split())

    M={0:0,1:D}

    def f(N):
        if N in M:
            return M[N]
        
        p,q=N//2*2,(N+1)//2*2
        r,s=N//3*3,(N+2)//3*3
        t,u=N//5*5,(N+4)//5*5
        R=min(D*N,
              D*abs(N-p)+A+f(p//2),
              D*abs(N-q)+A+f(q//2),
              
              D*abs(N-r)+B+f(r//3),
              D*abs(N-s)+B+f(s//3),
              
              D*abs(N-t)+C+f(t//5),
              D*abs(N-u)+C+f(u//5),
              )

        M[N]=R
        return R
    
    print(f(N))