from collections import defaultdict
import math
import heapq

f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")

T = int(f.readline())
test_cases = [list(map(int,f.readline().split())) for _ in range(T)]


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            devided1 = math.floor(checking/kake)
            devided2 = math.ceil(checking/kake)
            
            added_cost1 = cost + abs(math.floor(checking/kake)*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(math.ceil(checking/kake)*kake - checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    print(memo[0])

### FIXED CODE ###

from collections import defaultdict
import heapq

T = int(input())
test_cases = [list(map(int,input().split())) for _ in range(T)]


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            if checking%kake == 0:
                devided1 = checking//kake
                devided2 = checking//kake
            else:
                devided1 = checking//kake
                devided2 = checking//kake + 1
                
            #devided1 = math.floor(checking/kake)
            #devided2 = math.ceil(checking/kake)
            
            added_cost1 = cost + abs(devided1*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(devided2*kake-checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    print(memo[0])