Buggy python submission (verdict: Runtime Error):
def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    #2,3,5の場合それぞれ
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        check[x1]=-1
        if check[x1]>check[n]+x2*d+cha or check[x1]==-1:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #最寄りまで+1してく場合
        x1,x2=n//ttf+1,ttf-n%ttf
        check[x1]=-1
        if check[x1]>check[n]+x2*d+cha or check[x1]==-1:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    #2,3,5の場合それぞれ
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #最寄りまで+1してく場合
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        check[0]=min(check[n]+n*d,check[0])

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #最寄りまで+1してく場合
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    if n//ttf in check:
        if check[n//ttf]>check[n]+(n%ttf)*d+cha:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf)

    #最寄りまで+1してく場合
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=check[n]+n*d,check[0]
    if n//ttf in check:
        if check[n//ttf]>check[n]+(n%ttf)*d+cha:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=check[n]+n*d,check[0]
    if n//ttf in check:
        if check[n//ttf]>check[n]+(n%ttf)*d+cha:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,z,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global z
    for i,j in z:
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    z=list(zip([2,3,5],b))
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if check.get(x1) is not None:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if check.get(x1) is not None:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if check.get(x1) is None:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if check.get(x1) is None:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1==0:
        return
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    x3=x2*d
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x3:
                    check[x1]=check[n]+x3
            else:
                check[x1]=check[n]+x3
        else:
            if x1 in check:
                if check[x1]>check[n]+x3+cha:
                    check[x1]=check[n]+x3+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x3+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    x3=x2*d
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x3+cha:
                check[x1]=check[n]+x3+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x3+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    x1,x2,x3=n//ttf,n%ttf,x2*d
    x3=x2*d
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x3:
                    check[x1]=check[n]+x3
            else:
                check[x1]=check[n]+x3
        else:
            if x1 in check:
                if check[x1]>check[n]+x3+cha:
                    check[x1]=check[n]+x3+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x3+cha
                dfs(x1)

    x1,x2,x3=n//ttf+1,ttf-n%ttf,x2*d
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x3+cha:
                check[x1]=check[n]+x3+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x3+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if (ttf-n%ttf)>=(n%ttf):
        if n//ttf==0:
            if n//ttf in check:
                if check[n//ttf]>check[n]+(n%ttf)*d:
                    check[n//ttf]=check[n]+(n%ttf)*d
            else:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            if n//ttf in check:
                if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                    check[n//ttf]=check[n]+(n%ttf)*d+cha
                    dfs(n//ttf)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
    if (ttf-n%ttf)<=(n%ttf):
        if 1+n//ttf in check:
            if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
                check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
                dfs(1+n//ttf)
        else:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
def f(n):
 if (m:=s.get(n,-1))<0:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());a=2,3,5;s={0:0,1:d};print(f(n));"*int(input()))

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check[0]) if 0 in check else check[n]+n*d
    if n//ttf==0:
        check[n//ttf]=min(check[n]+(n%ttf)*d,check[n//ttf]) if n//ttf in check else check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])


Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**12
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**13
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**15
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(20)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(30)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(40)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(50)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Fixed submission:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])