def f(k):

    if k==1:return d

    if k==0:return 0

    if k in m:return m[k]

    s=min(k*d,f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d,f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d,f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)

    m[k]=s

    return s

for _ in range(int(eval(input()))):

    m={}

    n,a,b,c,d=list(map(int,input().split()))

    print((f(n)))
from functools import lru_cache

for _ in range(int(eval(input()))):

    n,a,b,c,d=list(map(int,input().split()))

    @lru_cache(None)

    def f(k):

        if k==0:return 0

        if k==1:return d

        return min(k*d,f(k//5)+c+k%5*d,f(k//3)+b+k%3*d,f(k//2)+a+k%2*d,f((k+4)//5)+c+-k%5*d,f((k+2)//3)+b+-k%3*d,f((k+1)//2)+a+-k%2*d)

    print((f(n)))
def f(k):
    if k == 1:
        return d
    if k == 0:
        return 0
    if k in m:
        return m[k]
    s = min(
        k * d,
        f(k // 2) + a + k % 2 * d,
        f((k + 1) // 2) + a + -k % 2 * d,
        f(k // 3) + b + k % 3 * d,
        f((k + 2) // 3) + b + -k % 3 * d,
        f(k // 5) + c + k % 5 * d,
        f((k + 4) // 5) + c + -k % 5 * d,
    )
    m[k] = s
    return s


for _ in range(int(eval(input()))):
    m = {}
    n, a, b, c, d = list(map(int, input().split()))
    print((f(n)))

from functools import lru_cache

for _ in range(int(eval(input()))):
    n, a, b, c, d = list(map(int, input().split()))

    @lru_cache(None)
    def f(k):
        if k == 0:
            return 0
        if k == 1:
            return d
        return min(
            k * d,
            f(k // 5) + c + k % 5 * d,
            f(k // 3) + b + k % 3 * d,
            f(k // 2) + a + k % 2 * d,
            f((k + 4) // 5) + c + -k % 5 * d,
            f((k + 2) // 3) + b + -k % 3 * d,
            f((k + 1) // 2) + a + -k % 2 * d,
        )

    print((f(n)))

-def f(k): -    if k == 1: -        return d -    if k == 0: -        return 0 -    if k in m: -        return m[k] -    s = min( -        k * d, -        f(k // 2) + a + k % 2 * d, -        f((k + 1) // 2) + a + -k % 2 * d, -        f(k // 3) + b + k % 3 * d, -        f((k + 2) // 3) + b + -k % 3 * d, -        f(k // 5) + c + k % 5 * d, -        f((k + 4) // 5) + c + -k % 5 * d, -    ) -    m[k] = s -    return s - +from functools import lru_cache -    m = {} + +    @lru_cache(None) +    def f(k): +        if k == 0: +            return 0 +        if k == 1: +            return d +        return min( +            k * d, +            f(k // 5) + c + k % 5 * d, +            f(k // 3) + b + k % 3 * d, +            f(k // 2) + a + k % 2 * d, +            f((k + 4) // 5) + c + -k % 5 * d, +            f((k + 2) // 3) + b + -k % 3 * d, +            f((k + 1) // 2) + a + -k % 2 * d, +        ) +