output_description: For each testcase, print the answer on Standard Output followed by a newline.
  
  * * *
input_description: The input is given from Standard Input. The first line of the input is
  
      
      
      T
      
  
  Then, T lines follow describing the T testcases. Each of the T lines has the
  format
  
      
      
      N A B C D
attempt: def estimateZeroToFive(A, B, C, D):
      List = [0] * 7
      List[1] = D
      List[2] = min(A + D, 2 * D)
      List[3] = min(3 * D, List[2] + D, List[1] + B)
      List[6] = min(6 * D, List[2] + B, List[3] + A, C + 2 * D)
      List[4] = min(4 * D, List[2] + A, List[3] + D, 2 * D + C, List[2] + B + 2 * D)
      List[5] = min(5 * D, List[1] + C, List[4] + D, List[6] + D, List[2] + B + D)
  
      return List
  
  
  def queue(Queue_CostValue):
      Values = Queue_CostValue.pop(0)
      return Values
  
  
  def OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns):
      while len(Queue_CostValue_Turns) > 0:
  
          CostValue = queue(Queue_CostValue_Turns)
  
          Cost = CostValue[0]
          Value = CostValue[1]
          CostMin = Acchieved[0]
          Flag = True
          if Cost > CostMin:
              Flag = False
          elif Value <= 6:
              Cost += Costs_ZeroToFive[Value]
              if Cost < CostMin:
                  Acchieved[0] = Cost
                  Flag = False
          if Flag == True:
              if Value % 5 == 0:
                  Queue_CostValue_Turns.append([Cost + C, Value // 5])
              if Value % 3 == 0:
                  Queue_CostValue_Turns.append([Cost + B, Value // 3])
              if Value % 2 == 0:
                  Queue_CostValue_Turns.append([Cost + A, Value // 2])
  
              Queue_CostValue_Turns.append([Cost + D, Value + 1])
              Queue_CostValue_Turns.append([Cost + D, Value - 1])
              OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns)
  
  
  def OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns):
      while len(Queue_CostValue_Turns) > 0:
  
          CostValue = queue(Queue_CostValue_Turns)
  
          Cost = CostValue[0]
          Value = CostValue[1]
          Turns = CostValue[2]
          CostMin = Acchieved[0]
          Flag = True
          if Cost > CostMin:
              Flag = False
          elif Value <= 6:
              Cost += Costs_ZeroToFive[Value]
              if Cost < CostMin:
  
                  Acchieved[0] = Cost
  
                  if len(Acchieved) == 1:
                      Acchieved.append(Turns)
                  else:
                      Acchieved[1] = Turns
                  Flag = False
          if Flag == True:
              if Value % 5 == 0:
                  Queue_CostValue_Turns.append([Cost + C, Value // 5, Turns + "C"])
              if Value % 3 == 0:
                  Queue_CostValue_Turns.append([Cost + B, Value // 3, Turns + "B"])
              if Value % 2 == 0:
                  Queue_CostValue_Turns.append([Cost + A, Value // 2, Turns + "A"])
  
              Queue_CostValue_Turns.append([Cost + D, Value + 1, Turns + "D+"])
              Queue_CostValue_Turns.append([Cost + D, Value - 1, Turns + "D-"])
              OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns)
  
  
  if __name__ == "__main__":
      # T = int( input().strip() )
      T = 1
      NABCDList = []
      for Num in range(T):
          StrList = input().strip().split()
          for m in range(len(StrList)):
              N = int(StrList[0])
              A = int(StrList[1])
              B = int(StrList[2])
              C = int(StrList[3])
              D = int(StrList[4])
  
          Costs_ZeroToFive = estimateZeroToFive(A, B, C, D)
          Acchieved = [N * D]
          # print("0-6: ", Costs_ZeroToFive)
          # OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, [ [0, N, ""] ])
          OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, [[0, N]])
          print(Acchieved[0])
          # estimatemin(N, A, B, C, D, N, Min, 0)
          # print(Min)
  
          # estimatemin(N, A, B, C, D, Value, Min, Coin_Used = 0):
  
problem_description: Statement
  
  You start with the number 0 and you want to reach the number N.
  
  You can change the number, paying a certain amount of coins, with the
  following operations:
  
    * Multiply the number by 2, paying A coins.
    * Multiply the number by 3, paying B coins.
    * Multiply the number by 5, paying C coins.
    * Increase or decrease the number by 1, paying D coins.
  
  You can perform these operations in arbitrary order and an arbitrary number of
  times.
  
  What is the minimum number of coins you need to reach N?
  
  **You have to solve T testcases.**
samples: [{"input": "5\n    11 1 2 4 8\n    11 1 2 2 8\n    32 10 8 5 4\n    29384293847243 454353412 332423423 934923490 1\n    900000000000000000 332423423 454353412 934923490 987654321", "output": "20\n    19\n    26\n    3821859835\n    23441258666\n    \n\nFor the first testcase, a sequence of moves that achieves the minimum cost of\n20 is:\n\n  * Initially x = 0.\n  * Pay 8 to increase by 1 (x = 1).\n  * Pay 1 to multiply by 2 (x = 2).\n  * Pay 1 to multiply by 2 (x = 4).\n  * Pay 2 to multiply by 3 (x = 12).\n  * Pay 8 to decrease by 1 (x = 11).\n\nFor the second testcase, a sequence of moves that achieves the minimum cost of\n19 is:\n\n  * Initially x = 0.\n  * Pay 8 to increase by 1 (x = 1).\n  * Pay 1 to multiply by 2 (x = 2).\n  * Pay 2 to multiply by 5 (x = 10).\n  * Pay 8 to increase by 1 (x = 11)."}]