T = int(input())
     
    caseList = []
     
    for i in range(T):
        caseList.append(list(map(int, input().split())))
        
    for N, A, B, C, D in caseList:
        i = 0
        nList = [N]
        costList = [0]
     
        allZeroFlag = False
        count=0
     
        prevMinAns=9999999999
        minAns=9999999999
     
        while not allZeroFlag:
            allZeroFlag = True
     
            tmpNList=[]
            tmpCostList=[]
     
            for i in range(len(nList)):
                if nList[i] == 0:
                    continue
                allZeroFlag = False
     
                tmpNList += [nList[i] + 1, nList[i] - 1]
                tmpCostList += [costList[i]+D, costList[i]+D]
     
                if nList[i] % 5 == 0:
                    tmpNList.append(nList[i]//5)
                    tmpCostList.append(costList[i]+C)
     
                if nList[i] % 3 == 0:
                    tmpNList.append(nList[i]//3)
                    tmpCostList.append(costList[i]+B)
     
                if nList[i] % 2 == 0:
                    tmpNList.append(nList[i]//2)
                    tmpCostList.append(costList[i]+A)
     
            nList=tmpNList
            costList = tmpCostList
     
            ans=[]
            for i,ni in enumerate(nList):
                if ni == 0:
                    ans.append(costList[i])
     
            try:
                minAns = min(ans)
            except:
                pass
     
            count+=1
            if prevMinAns<minAns:break
            prevMinAns = minAns
     
        print(prevMinAns)

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))
    
for N, A, B, C, D in caseList:
    dic = {N: 0}
	minAns = 999999999999
	searchSet = set([N])

	count = 0
	k=N
	while True:
 	   tmpSet = set()

      v = dic[k]

      if k == 1:
          continue

      # A
      if k % 2 == 0:
          dic[k // 2] = dic.get(k // 2, minAns)
          if dic[k // 2] > v + A:
              dic[k // 2] = v + A
              tmpSet.add(k // 2)

      # B
      if k % 3 == 0:
          dic[k // 3] = dic.get(k // 3, minAns)
          if dic[k // 3] > v + B:
              dic[k // 3] = v + B
              tmpSet.add(k // 3)

      # C
      if k % 5 == 0:
          dic[k // 5] = dic.get(k // 5, minAns)
          if dic[k // 5] > v + C:
              dic[k // 5] = v + C
              tmpSet.add(k // 5)

      # D
      dic[k + 1] = dic.get(k + 1, minAns)
      if dic[k + 1] > v + D:
          dic[k + 1] = v + D
          tmpSet.add(k + 1)

      dic[k - 1] = dic.get(k - 1, minAns)
      if dic[k - 1] > v + D:
          dic[k - 1] = v + D
          tmpSet.add(k - 1)

      del dic[k]
      k=min(dic, key=dic.get)


      count += 1
      if 1 in dic.keys():
          if minAns > dic[1] + D:
              minAns = dic[1] + D
          #             print(minAns)
          else:
              break
	print(minAns)

### FIXED CODE ###

from functools import lru_cache

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))


@lru_cache(maxsize=None)
def solve(n, A, B, C, D):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n == 2:
        return min(D + D, A + D)

    ans = n * D

    for num, cost in zip([2, 3, 5], [A, B, C]):
        ans = min(
            solve((n + (num - n % num)) // num, A, B, C, D) + cost + D * (num - n % num),
            solve((n - n % num) // num, A, B, C, D) + cost + D * (n % num),
            ans,
        )

    return ans


for N, A, B, C, D in caseList:
    print(solve(N, A, B, C, D))