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):

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

    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:
        m = d * n
        for p, c in zip(a, b):
            m = min(m, *(f(k) + abs(p * k - n) * d + c for k in (n // p, -(-n // p))))
        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)))

-            m = min(m, *(f(k) + abs(p * k - n) * d + c for k in (n // p, -(-n // p)))) +            k, r = divmod(n, p) +            m = min(m, f(k) + r * d + c, r and f(k + 1) + (p - r) * d + c or m)