T=int(eval(input()))

for i in range(T):

    N,A,B,C,D=list(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)))
T=int(eval(input()))



X=[]

for i in range(T):

    N,A,B,C,D=list(map(int,input().split()))



    M={0:0,1:D}

    S={2:A,3:B,5:C}

    

    def f(N):

        if N in M:

            return M[N]

        

        R=D*N

        for k in S:

            p,q=N//k*k,(N+k-1)//k*k

            R=min(R,

                  D*abs(N-p)+S[k]+f(p//k),

                  D*abs(N-q)+S[k]+f(q//k)

                  )



        M[N]=R

        return R



    X.append(f(N))

print(("\n".join(map(str,X))))

T = int(eval(input()))
for i in range(T):
    N, A, B, C, D = list(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)))

T = int(eval(input()))
X = []
for i in range(T):
    N, A, B, C, D = list(map(int, input().split()))
    M = {0: 0, 1: D}
    S = {2: A, 3: B, 5: C}

    def f(N):
        if N in M:
            return M[N]
        R = D * N
        for k in S:
            p, q = N // k * k, (N + k - 1) // k * k
            R = min(
                R, D * abs(N - p) + S[k] + f(p // k), D * abs(N - q) + S[k] + f(q // k)
            )
        M[N] = R
        return R

    X.append(f(N))
print(("\n".join(map(str, X))))

+X = [] +    S = {2: A, 3: B, 5: C} -        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), -        ) +        R = D * N +        for k in S: +            p, q = N // k * k, (N + k - 1) // k * k +            R = min( +                R, D * abs(N - p) + S[k] + f(p // k), D * abs(N - q) + S[k] + f(q // k) +            ) -    print((f(N))) +    X.append(f(N)) +print(("\n".join(map(str, X))))