### BUGGY CODE ###

from collections import deque,defaultdict
class DFS:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.Q = deque([[n,0]])
        self.memory = defaultdict(int) # 実績を記録、すでにその値より低いコストでやっていたら除外する
    def dfs(self):
        while self.Q:
#             from IPython.core.debugger import Pdb; Pdb().set_trace()
            num,cost = self.Q.popleft()
            if num == 0:
                self.ans = min(self.ans, cost)
            elif num == 1:
                self.ans = min(self.ans, cost + self.D * num)
            else:
                # 5の倍数に上げて5で割った場合
                temp_num = num//5 + 1
                temp_cost = cost + ((num//5 + 1) * 5 - num) * self.D + self.C
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に上げて3で割った場合
                temp_num = num//3 + 1
                temp_cost = cost + ((num//3 + 1) * 3 - num) * self.D + self.B
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                    
                # 2の倍数に上げて2で割った場合
                temp_num = num//2 + 1
                temp_cost = cost + ((num//2 + 1) * 2 - num) * self.D + self.A
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 全て引いた場合
                self.ans = min(self.ans, num*self.D + cost)
                
        return self.ans
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    case = DFS(N,A,B,C,D)
    print(case.dfs())

### FIXED CODE ###

from collections import defaultdict,deque
class dfs:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.memory = defaultdict(int)
        self.Q = deque([[self.N,0]])
    def dfs(self):
        while self.Q:
            num,cost = self.Q.popleft()
            if self.memory[num] > cost :
                pass
            else:
                if num == 0:
                    self.ans = min(self.ans,cost)
                elif num == 1:
                    self.ans = min(self.ans,cost+self.D)
                else:
                    for step,a_cost in [[2,self.A],[3,self.B],[5,self.C]]:
                        if num % step != 0:
                            temp_num = (num//step)+1
                            temp_cost = cost + (((num//step)+1)*step - num) * self.D + a_cost
                            self.memo_check_append(temp_num,temp_cost)
                        temp_num = num//step
                        temp_cost = cost + (num - (num//step)*step) * self.D + a_cost
                        self.memo_check_append(temp_num,temp_cost)
                    self.ans = min(self.ans,cost + num * self.D)
        return self.ans
    def memo_check_append(self,n,c):
        if self.memory[n] > c or self.memory[n] == 0:
            self.Q.append([n,c])
            self.memory[n] = c

N = int(input())
for _ in range(N):
  N,A,B,C,D = map(int,input().split())
  T = dfs(N,A,B,C,D)
  print(T.dfs())