import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


T = int(sys.stdin.buffer.readline())
NABCD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(T)]


def solve2(N, A, B, C, D):
    heap = []
    dist = defaultdict(lambda: INF)
    dist[0] = 0
    dist[N] = D * N
    heapq.heappush(heap, (0, 0))
    while heap:
        cnt, n = heapq.heappop(heap)
        if dist[N] <= cnt:
            break
        if dist[n] < cnt:
            continue
        if n == N:
            break
        if n > N:
            dist[n] = cnt + abs(N - n)
        if cnt + A < dist[n * 2]:
            dist[n * 2] = cnt + A
            heapq.heappush(heap, (cnt + A, n * 2))
        if cnt + B < dist[n * 3]:
            dist[n * 3] = cnt + B
            heapq.heappush(heap, (cnt + B, n * 3))
        if cnt + C < dist[n * 5]:
            dist[n * 5] = cnt + C
            heapq.heappush(heap, (cnt + C, n * 5))
        if cnt + D < dist[n + 1]:
            dist[n + 1] = cnt + D
            heapq.heappush(heap, (cnt + D, n + 1))
        if cnt + D < dist[n - 1] and n - 1 > 0:
            dist[n - 1] = cnt + D
            heapq.heappush(heap, (cnt + D, n - 1))
    return dist[N]


def solve(N, A, B, C, D):
    dist = defaultdict(lambda: INF)
    dist[N] = 0
    # dist[0] = N * D
    heap = [(0, N)]
    while heap:
        cnt, n = heapq.heappop(heap)
        if dist[n] < cnt:
            continue
        if n <= 5:
            dist[0] = min(dist[0], cnt + n * D)

        if cnt + abs(n - n // 2) * D < dist[n // 2]:
            dist[n // 2] = cnt + abs(n - n // 2) * D
            heapq.heappush(heap, (cnt + abs(n - n // 2) * D, n // 2))
        if cnt + abs(n - n // 3) * D < dist[n // 3]:
            dist[n // 3] = cnt + abs(n - n // 3) * D
            heapq.heappush(heap, (cnt + abs(n - n // 3) * D, n // 3))
        if cnt + abs(n - n // 5) * D < dist[n // 5]:
            dist[n // 5] = cnt + abs(n - n // 5) * D
            heapq.heappush(heap, (cnt + abs(n - n // 5) * D, n // 5))

        l = n // 2 * 2
        d = A + abs(l - n) * D
        if A < abs(n - l // 2) * D and cnt + d < dist[l // 2]:
            dist[l // 2] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 2))
        r = l + 2
        d = A + abs(r - n) * D
        if A < abs(n - r // 2) * D and cnt + d < dist[r // 2]:
            dist[r // 2] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 2))

        l = n // 3 * 3
        d = B + abs(l - n) * D
        if B < abs(n - l // 3) * D and cnt + d < dist[l // 3]:
            dist[l // 3] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 3))
        r = l + 3
        d = B + abs(r - n) * D
        if B < abs(n - r // 3) * D and cnt + d < dist[r // 3]:
            dist[r // 3] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 3))

        l = n // 5 * 5
        d = C + abs(l - n) * D
        if C < abs(n - l // 5) * D and cnt + d < dist[l // 5]:
            dist[l // 5] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 5))
        r = l + 5
        d = C + abs(r - n) * D
        if C < abs(n - r // 5) * D and cnt + d < dist[r // 5]:
            dist[r // 5] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 5))

    return dist[0]


for r in NABCD:
    ans = solve(*r)
    print(ans)


Measured memory_bytes: 124768