### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)    

def vc(value,cost,pt):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return value,cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost
#    elif value==1:
#        cost=cost+d
#        return value,cost        
    
    if pt==1:
        v=value//2
        cost=cost+a+(value-v*2)*d
    elif pt==2:
        v=value//3
        cost=cost+b+(value-v*3)*d
    elif pt==3:
        v=value//5
        cost=cost+c+(value-v*5)*d
    elif pt==4:
        v=value//2+1
        cost=cost+a+(v*2-value)*d
    elif pt==5:
        v=value//3+1
        cost=cost+b+(v*3-value)*d
    elif pt==6:
        v=value//5+1
        cost=cost+c+(v*5-value)*d
    elif pt==7:
        v=0
        cost=cost+(value-v)*d
    return v,cost
    
def dfc(value,cost):
#    print(value,cost)
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost

    for i in range(7):
        value1,cost1=vc(value,cost,i+1)
#        print(i+1,":",value1,cost1)
        if value1 in vcs.keys():
            if vcs[value1]<=cost1:
                continue
            else:
                vcs[value1]=min(vcs[value1],cost1)     
                dfc(value1,cost1)
        else:
            vcs[value1]=cost1     
            dfc(value1,cost1)
        
'''          
    value1,cost1=vc(value,cost,1)
    print("1:",value1,cost1)
    if value1 in vcs.keys():
        vcs[value1]=min(vcs[value1],cost1)     
    else:
        vcs[value1]=cost1     
        dfc(value1,cost1)

    value2,cost2=vc(value,cost,2)
    print("2:",value2,cost2)
    if value2 in vcs.keys():
        vcs[value2]=min(vcs[value2],cost2)        
    else:
        vcs[value2]=cost2     
        dfc(value2,cost2)

    value3,cost3=vc(value,cost,3)
    print("3:",value3,cost3)
    if value3 in vcs.keys():
        vcs[value3]=min(vcs[value3],cost3)        
    else:
        vcs[value3]=cost3     
        dfc(value3,cost3)

    value4,cost4=vc(value,cost,4)
    print("4:",value4,cost4)
    if value4 in vcs.keys():
        vcs[value4]=min(vcs[value4],cost4)        
    else:
        vcs[value4]=cost4     
        dfc(value4,cost4)

    value5,cost5=vc(value,cost,5)
    print("5:",value5,cost5)
    if value5 in vcs.keys():
        vcs[value5]=min(vcs[value5],cost5)        
    else:
        vcs[value5]=cost5     
        dfc(value5,cost5)

    value6,cost6=vc(value,cost,6)
    print("6:",value6,cost6)
    if value6 in vcs.keys():
        vcs[value6]=min(vcs[value6],cost6)        
    else:
        vcs[value6]=cost6     
        dfc(value6,cost6)
    
    value7,cost7=vc(value,cost,7)
    print("7:",value7,cost7)
    if value7 in vcs.keys():
        vcs[value7]=min(vcs[value7],cost7)        
    else:
        vcs[value7]=cost7     
        dfc(value7,cost7)
'''

t=int(input())
#t=1
for i in range(t):
    n,a,b,c,d=map(int,input().split())
#    n,a,b,c,d=11,1,2,4,8
#    n,a,b,c,d=11,1,2,2,8
#    n,a,b,c,d=32, 10, 8, 5, 4
#    n,a,b,c,d=29384293847243, 454353412, 332423423, 934923490, 1
#    n,a,b,c,d=900000000000000000, 332423423, 454353412, 934923490, 987654321
    
    vcs=dict()

    cost=dfc(n,0)

#    print(cost)
#    print(min(vcs.items()))
    print(vcs[0])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)    

def vc(value,cost,pt):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return value,cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost
    
    if pt==1:
        v=value//2
        cost=cost+a+(value-v*2)*d
    elif pt==2:
        v=value//3
        cost=cost+b+(value-v*3)*d
    elif pt==3:
        v=value//5
        cost=cost+c+(value-v*5)*d
    elif pt==4:
        v=value//2+1
        cost=cost+a+(v*2-value)*d
    elif pt==5:
        v=value//3+1
        cost=cost+b+(v*3-value)*d
    elif pt==6:
        v=value//5+1
        cost=cost+c+(v*5-value)*d
    elif pt==7:
        v=0
        cost=cost+(value-v)*d
    return v,cost
    
def dfc(value,cost):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost

    for i in range(7):
        value1,cost1=vc(value,cost,i+1)
#        print(i+1,":",value1,cost1)
        if value1 in vcs.keys():
            if vcs[value1]<=cost1:
                continue
            else:
                vcs[value1]=min(vcs[value1],cost1)     
                dfc(value1,cost1)
        else:
            vcs[value1]=cost1     
            dfc(value1,cost1)
        

t=int(input())
#t=1
for i in range(t):
    n,a,b,c,d=map(int,input().split())
#    n,a,b,c,d=11,1,2,4,8
#    n,a,b,c,d=11,1,2,2,8
#    n,a,b,c,d=32, 10, 8, 5, 4
#    n,a,b,c,d=29384293847243, 454353412, 332423423, 934923490, 1
#    n,a,b,c,d=900000000000000000, 332423423, 454353412, 934923490, 987654321
    
    vcs=dict()
    cost=dfc(n,0)
    print(vcs[0])