Buggy python submission (verdict: Runtime Error):
import re
from collections import defaultdict
import sys
#from Levenshtein import distance as ldist

def tableexp(n):
    res=[0]*(n+1)
    res[2]=1
    res2=[0]*(n+1)
    res2[2]=1
    res3=[0]*(n+1)
    res3[2]=0
    for i in range(3,n+1):
        js=sorted(list(range(1,i)),key = lambda j:j/i*res[j]+(i-j)/i*res[i-j])
        j=js[0]
        res[i]=1+j/i*res[j]+(i-j)/i*res[i-j]
        jj=i//2
        res2[i]=1+jj/i*res2[jj]+(i-jj)/i*res2[i-jj]
        js=sorted(list(range(1,i)),key = lambda j:j*j/i/i*res[j]+(i-j)/i*res[i-j])
        print(i,j,jj,res[i],res2[i])
    return res


    

def placer(lettre,n,poss, printme=True):
    if n==0:
        return [],0
    if n==len(poss):
         return poss,0
    else:
        totry="".join([lettre if i in poss[:len(poss)//2] and i not in realpresence else fs[i] for i in range(lenstr)])
        testres=lenstr-minpresence-wheretotest(totry)
        a=placer(lettre,testres,poss[:len(poss)//2],printme=False)
        b=placer(lettre,n-testres,poss[len(poss)//2:],printme=False)
        if printme:
            print(lettre,a[0]+b[0],a[1]+b[1]+1)
        return (a[0]+b[0],a[1]+b[1]+1)


lettres="abcdefghijklmnopqrstuvwxyz"
lettres+=lettres.upper()
lettres+="1234567890"


def testatc(s):
    print("?", s)
    sys.stdout.flush()
    ans=int(input())
    return ans

def maxrepresentee(s):
    d=defaultdict(int)
    for k in s:
        d[k]+=1
    return(max(d.values()))

def reps(s):
    d=defaultdict(int)
    for k in s:
        d[k]+=1
    return(d.values())

def testlocal(s):
    print(s,ldist(s,sb))
    return ldist(s,sb)

nbcall=0
def wheretotest(s):
    global nbcall
    nbcall+=1
    return testatc(s)

nb_methodes=4

dd=defaultdict(int)
nb_simus=1


drbest=defaultdict(int)



for sb in ["AtCod3rIsGreat"]:
    lestrdef=False
    lenstr=128
    minpresence=lenstr
    moinspresente=None
    #methode 4 : on place chaque lettre
    dp={} #determiner chaque lettre
    tr=0
    for i in lettres:
        nbi=lenstr-wheretotest(i*lenstr)
        #print(i,nbi)
        if nbi and not lestrdef:
            lenstr=wheretotest(i*nbi)+nbi
            lestrdef=True
       # print("testing",i*lenstr)
        tr+=1
        #if nbi:
        #    print(i, "y est ",nbi)
        if nbi:
            dp[i]=nbi
        if nbi<minpresence:
            minpresence=nbi
            moinspresente=i
        if sum(dp.values())==lenstr: #2.4 soumissions en moyenne de gain
            break
        if tr==len(lettres)-1: #on connait le dernier après les 61 faits. ca devrait rapporter 0.4 soumissions en moyenne.
            dp[lettres[-1]]=lenstr-sum(dp.values())
            """if lenstr-sum(dp.values()):
                print(lettres[-1], "y est ",nbi)"""
            break
    
    #determiner une fakestring
    realpresence=set()
    fs=moinspresente*lenstr
    if minpresence:
        fs=moinspresente*lenstr
        bfs=lenstr-dp[moinspresente]
        for i in range(lenstr):
            ffs="".join([fs[k] if k!=i else ("b" if moinspresente!="b" else "c") for k in range(lenstr)])
            ans=wheretotest(ffs)
            if ans>bfs:
                realpresence.add(i)
    assert(minpresence==len(realpresence))
    ss=[None]*lenstr
    for i in realpresence:
        ss[i]=moinspresente
    poss=list(range(lenstr))
    keysleft=len(dp)- (1 if minpresence else 0)
    keyss=sorted(dp.keys(), key=lambda x:-dp[x])
    for ii in range(len(keyss)):
        i=keyss[ii]
        if i!=moinspresente:
            if keysleft!=2 or dp[keyss[ii]]+dp[keyss[ii+1]]!=2:
                p=placer(i,dp[i],poss,False)
                tr+=p[1]
                for k in p[0]:
                    ss[k]=i
                    poss=[j for j in poss if j!=k]
                if keysleft==1:
                    s="".join(ss)
            else:
                ss1=ss[:]
                ss2=ss[:]
                poss=[keyss[ii],keyss[ii+1]]
                p1,p2=[k for k in range(lenstr) if ss[k] is None]
                ss1[p1]=i
                ss2[p2]=i
                ss1[p2]=keyss[ii+1]
                ss2[p1]=keyss[ii+1]
                if wheretotest("".join(ss1)):
                    tr+=1
                    assert(wheretotest("".join(ss2)))==0
                    s="".join(ss2)
                else:
                    s="".join(ss1)
                break
            keysleft-=1
    print("!",s)
    sys.stdout.flush()


    


Fixed submission:

t=int(input())
for nt in range(t):
    n,a,b,c,d=[int(k) for k in input().strip().split(" ")]
    r={0:0}
    z=[0,0,a,b,0,c]
    steps=0
    def solve(k):
        #print("solving for",k)
        global r
     #   global steps
        if k in r:
            return r[k]
        else:
            res=k*d
            for i in [2,3,5]:
                if not k%i:
                    res=min(res,z[i]+solve(k//i))
                else:
                    res=min(res,solve(k//i)+z[i]+d*(k%i))
                    if (k//i+1)<k:
                        res=min(res,solve(k//i+1)+z[i]+d*(i-k%i))
     #   print("solved for",k,res)
     #   steps+=1
        r[k]=res
        return res
    print(solve(n))
    #print("steps",steps)