import sys

sys.setrecursionlimit(10**7)

def dfs(x):

    if x == 0:

        return 0

    if x == 1:

        return d

    if x in dic:

        return dic[x]

    l2 = x//2

    r2 = (x+1)//2

    l3 = x//3

    r3 = (x+2)//3

    l5 = x//5

    r5 = (x+4)//5

    count = min(x*d,10**18)

    count = min(count,abs(l2*2-x)*d+a+dfs(l2))

    count = min(count,abs(r2*2-x)*d+a+dfs(r2))

    count = min(count,abs(l3*3-x)*d+b+dfs(l3))

    count = min(count,abs(r3*3-x)*d+b+dfs(r3))

    count = min(count,abs(l5*5-x)*d+c+dfs(l5))

    count = min(count,abs(r5*5-x)*d+c+dfs(r5))

    dic[x] = count

    return count



t = int(eval(input()))

for _ in range(t):

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

    dic = {}

    print((dfs(n)))
import sys

from functools import lru_cache

sys.setrecursionlimit(10**7)



def solve(x,a,b,c,d):

    @lru_cache(None)

    def dfs(x):

        if x == 0:

            return 0

        if x == 1:

            return d

        l2 = x//2

        r2 = (x+1)//2

        l3 = x//3

        r3 = (x+2)//3

        l5 = x//5

        r5 = (x+4)//5

        count = x*d

        count = min(count,abs(l2*2-x)*d+a+dfs(l2))

        count = min(count,abs(r2*2-x)*d+a+dfs(r2))

        count = min(count,abs(l3*3-x)*d+b+dfs(l3))

        count = min(count,abs(r3*3-x)*d+b+dfs(r3))

        count = min(count,abs(l5*5-x)*d+c+dfs(l5))

        count = min(count,abs(r5*5-x)*d+c+dfs(r5))

        return count

    return dfs(x)

t = int(eval(input()))

for _ in range(t):

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

    print((solve(n,a,b,c,d)))
import sys

sys.setrecursionlimit(10**7)


def dfs(x):
    if x == 0:
        return 0
    if x == 1:
        return d
    if x in dic:
        return dic[x]
    l2 = x // 2
    r2 = (x + 1) // 2
    l3 = x // 3
    r3 = (x + 2) // 3
    l5 = x // 5
    r5 = (x + 4) // 5
    count = min(x * d, 10**18)
    count = min(count, abs(l2 * 2 - x) * d + a + dfs(l2))
    count = min(count, abs(r2 * 2 - x) * d + a + dfs(r2))
    count = min(count, abs(l3 * 3 - x) * d + b + dfs(l3))
    count = min(count, abs(r3 * 3 - x) * d + b + dfs(r3))
    count = min(count, abs(l5 * 5 - x) * d + c + dfs(l5))
    count = min(count, abs(r5 * 5 - x) * d + c + dfs(r5))
    dic[x] = count
    return count


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

import sys
from functools import lru_cache

sys.setrecursionlimit(10**7)


def solve(x, a, b, c, d):
    @lru_cache(None)
    def dfs(x):
        if x == 0:
            return 0
        if x == 1:
            return d
        l2 = x // 2
        r2 = (x + 1) // 2
        l3 = x // 3
        r3 = (x + 2) // 3
        l5 = x // 5
        r5 = (x + 4) // 5
        count = x * d
        count = min(count, abs(l2 * 2 - x) * d + a + dfs(l2))
        count = min(count, abs(r2 * 2 - x) * d + a + dfs(r2))
        count = min(count, abs(l3 * 3 - x) * d + b + dfs(l3))
        count = min(count, abs(r3 * 3 - x) * d + b + dfs(r3))
        count = min(count, abs(l5 * 5 - x) * d + c + dfs(l5))
        count = min(count, abs(r5 * 5 - x) * d + c + dfs(r5))
        return count

    return dfs(x)


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

+from functools import lru_cache -def dfs(x): -    if x == 0: -        return 0 -    if x == 1: -        return d -    if x in dic: -        return dic[x] -    l2 = x // 2 -    r2 = (x + 1) // 2 -    l3 = x // 3 -    r3 = (x + 2) // 3 -    l5 = x // 5 -    r5 = (x + 4) // 5 -    count = min(x * d, 10**18) -    count = min(count, abs(l2 * 2 - x) * d + a + dfs(l2)) -    count = min(count, abs(r2 * 2 - x) * d + a + dfs(r2)) -    count = min(count, abs(l3 * 3 - x) * d + b + dfs(l3)) -    count = min(count, abs(r3 * 3 - x) * d + b + dfs(r3)) -    count = min(count, abs(l5 * 5 - x) * d + c + dfs(l5)) -    count = min(count, abs(r5 * 5 - x) * d + c + dfs(r5)) -    dic[x] = count -    return count +def solve(x, a, b, c, d): +    @lru_cache(None) +    def dfs(x): +        if x == 0: +            return 0 +        if x == 1: +            return d +        l2 = x // 2 +        r2 = (x + 1) // 2 +        l3 = x // 3 +        r3 = (x + 2) // 3 +        l5 = x // 5 +        r5 = (x + 4) // 5 +        count = x * d +        count = min(count, abs(l2 * 2 - x) * d + a + dfs(l2)) +        count = min(count, abs(r2 * 2 - x) * d + a + dfs(r2)) +        count = min(count, abs(l3 * 3 - x) * d + b + dfs(l3)) +        count = min(count, abs(r3 * 3 - x) * d + b + dfs(r3)) +        count = min(count, abs(l5 * 5 - x) * d + c + dfs(l5)) +        count = min(count, abs(r5 * 5 - x) * d + c + dfs(r5)) +        return count + +    return dfs(x) -    dic = {} -    print((dfs(n))) +    print((solve(n, a, b, c, d)))