# coding: utf-8

from collections import defaultdict





def solve(*args: str) -> str:

    t = int(args[0])

    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]



    ret = []

    for n, a, b, c, d in NABCD:

        ABC = ((2, a), (3, b), (5, c))

        dp = defaultdict(lambda: n*d)

        stack = [(n, 0)]

        while stack:

            rem, cost = stack.pop()

            if min(dp[0], dp[rem]) <= cost:

                continue



            dp[rem] = cost

            dp[0] = min(dp[0], cost+rem*d)



            if 0 < rem:

                for x, y in ABC:

                    l, h = rem//x, -(-rem//x)

                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))

                    stack.append((h, d*abs(h*x-rem)+cost+y))



        ret.append(str(dp[0]))



    return '\n'.join(ret)





if __name__ == "__main__":

    print((solve(*(open(0).read().splitlines()))))

# coding: utf-8

from collections import defaultdict





def solve(*args: str) -> str:

    t = int(args[0])

    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]



    ret = []

    for n, a, b, c, d in NABCD:

        ABC = ((2, a), (3, b), (5, c))

        dp = defaultdict(lambda: n*d)

        stack = [(n, 0)]

        while stack:

            rem, cost = stack.pop()

            if min(dp[0], dp[rem]) <= cost:

                continue



            dp[rem] = cost

            dp[0] = min(dp[0], cost+rem*d)



            if 0 < rem:

                for x, y in ABC:

                    div, m = divmod(rem, x)

                    if div:

                        stack.append((div, d*m+cost+y))

                    if m:

                        stack.append((div+1, d*(x-m)+cost+y))



        ret.append(str(dp[0]))



    return '\n'.join(ret)





if __name__ == "__main__":

    print((solve(*(open(0).read().splitlines()))))

# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]
    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n * d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue
            dp[rem] = cost
            dp[0] = min(dp[0], cost + rem * d)
            if 0 < rem:
                for x, y in ABC:
                    l, h = rem // x, -(-rem // x)
                    stack.append((l, d * abs(l * x - rem) + cost + y * (0 < l)))
                    stack.append((h, d * abs(h * x - rem) + cost + y))
        ret.append(str(dp[0]))
    return "\n".join(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))

# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]
    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n * d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue
            dp[rem] = cost
            dp[0] = min(dp[0], cost + rem * d)
            if 0 < rem:
                for x, y in ABC:
                    div, m = divmod(rem, x)
                    if div:
                        stack.append((div, d * m + cost + y))
                    if m:
                        stack.append((div + 1, d * (x - m) + cost + y))
        ret.append(str(dp[0]))
    return "\n".join(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))

-                    l, h = rem // x, -(-rem // x) -                    stack.append((l, d * abs(l * x - rem) + cost + y * (0 < l))) -                    stack.append((h, d * abs(h * x - rem) + cost + y)) +                    div, m = divmod(rem, x) +                    if div: +                        stack.append((div, d * m + cost + y)) +                    if m: +                        stack.append((div + 1, d * (x - m) + cost + y))