### BUGGY CODE ###

import heapq
def main():
    T = int(input())
    ans = [None]*T
    ipt = [list(map(int, input().split())) for _ in range(T)]
    for i in range(T):
        n, a, b, c, d = ipt[i]
        dic = {}
        dic[n] = 0
        hq = [-n]
        heapq.heapify(hq)
        while len(hq) > 0:
            p = heapq.heappop(hq)
            p *= -1
            for x in range(p-5, p+6):
                if x <= 1:
                    continue
                if x%2 == 0:
                    if not x//2 in dic:
                        dic[x//2] = float("inf")
                        heapq.heappush(hq, -1*(x//2))
                    if dic[p]+d*abs(x-p)+a < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(x-p)+a
                    if dic[p]+d*abs(p-x//2) < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(p-x//2)
                if x%3 == 0:
                    if not x//3 in dic:
                        dic[x//3] = float("inf")
                        heapq.heappush(hq, -1*(x//3))
                    if dic[p]+d*abs(x-p)+b < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(x-p)+b
                    if dic[p]+d*abs(p-x//3) < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(p-x//3)
                if x%5 == 0:
                    if not x//5 in dic:
                        dic[x//5] = float("inf")
                        heapq.heappush(hq, -1*(x//5))
                    if dic[p]+d*abs(x-p)+c < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(x-p)+c
                    if dic[p]+d*abs(p-x//5) < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(p-x//5)
        ans[i] = min(n*d, dic[1]+d)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
def main():
    T = int(input())
    ans = [None]*T
    ipt = [list(map(int, input().split())) for _ in range(T)]
    for i in range(T):
        n, a, b, c, d = ipt[i]
        dic = {}
        dic[n] = 0
        hq = [-n]
        heapq.heapify(hq)
        while len(hq) > 0:
            p = heapq.heappop(hq)
            p *= -1
            for x in range(p-5, p+6):
                if x <= 1:
                    continue
                if x%2 == 0:
                    if not x//2 in dic:
                        dic[x//2] = float("inf")
                        heapq.heappush(hq, -1*(x//2))
                    if dic[p]+d*abs(x-p)+a < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(x-p)+a
                    if dic[p]+d*abs(p-x//2) < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(p-x//2)
                if x%3 == 0:
                    if not x//3 in dic:
                        dic[x//3] = float("inf")
                        heapq.heappush(hq, -1*(x//3))
                    if dic[p]+d*abs(x-p)+b < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(x-p)+b
                    if dic[p]+d*abs(p-x//3) < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(p-x//3)
                if x%5 == 0:
                    if not x//5 in dic:
                        dic[x//5] = float("inf")
                        heapq.heappush(hq, -1*(x//5))
                    if dic[p]+d*abs(x-p)+c < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(x-p)+c
                    if dic[p]+d*abs(p-x//5) < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(p-x//5)
        ans[i] = min(n*d, dic[1]+d)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()