a = 2, 3, 5



def f(n):

  m = memo.get(n)

  if m is None:

    s = {(0, 0, 0)}.union(*({(n // p, p, c), (-(-n // p), p, c)} for p, c in zip(a, b)))

    m = min(f(x) + abs(x * p - n) * d + c for x, p, c in s)

    memo[n] = m

  return m



t = int(eval(input()))

for _ in range(t):

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

  memo = {0: 0, 1: d}

  print((f(n)))

a = 2, 3, 5



def f(n):

  m = memo.get(n)

  if m is None:

    m = d * n

    for p, c in zip(a, b):

      k, r = divmod(n, p);

      m = min(m, f(k) + r * d + c, r  and f(k + 1) + (p - r) * d + c or m)

    memo[n] = m

  return m



t = int(eval(input()))

for _ in range(t):

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

  memo = {0: 0, 1: d}

  print((f(n)))

a = 2, 3, 5


def f(n):
    m = memo.get(n)
    if m is None:
        s = {(0, 0, 0)}.union(
            *({(n // p, p, c), (-(-n // p), p, c)} for p, c in zip(a, b))
        )
        m = min(f(x) + abs(x * p - n) * d + c for x, p, c in s)
        memo[n] = m
    return m


t = int(eval(input()))
for _ in range(t):
    n, *b, d = list(map(int, input().split()))
    memo = {0: 0, 1: d}
    print((f(n)))

a = 2, 3, 5


def f(n):
    m = memo.get(n)
    if m is None:
        m = d * n
        for p, c in zip(a, b):
            k, r = divmod(n, p)
            m = min(m, f(k) + r * d + c, r and f(k + 1) + (p - r) * d + c or m)
        memo[n] = m
    return m


t = int(eval(input()))
for _ in range(t):
    n, *b, d = list(map(int, input().split()))
    memo = {0: 0, 1: d}
    print((f(n)))

-        s = {(0, 0, 0)}.union( -            *({(n // p, p, c), (-(-n // p), p, c)} for p, c in zip(a, b)) -        ) -        m = min(f(x) + abs(x * p - n) * d + c for x, p, c in s) +        m = d * n +        for p, c in zip(a, b): +            k, r = divmod(n, p) +            m = min(m, f(k) + r * d + c, r and f(k + 1) + (p - r) * d + c or m)