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 search_root(item):
      min = 23441258667
      money = search(item, min, 8, 1, 1)
      if money < min:
          min = money
      print(min)
  
  
  def search(item, min, money, n, depth):
      min_value = 23441258667
      if depth == 100:
          return 23441258667
      if item[0] == n:
          return money
      if n < 1:
          return 23441258667
      if min < money:
          return 23441258667
      if item[0] + 4 < n:
          return 23441258667
      for i in range(1, 4):
          min_value = search(item, min, money + item[i], n * index_list[i], depth + 1)
          if min > min_value:
              min = min_value
      min_value = search(item, min, money + item[4], n + 1, depth + 1)
      if min > min_value:
          min = min_value
      min_value = search(item, min, money + item[4], n - 1, depth + 1)
      if min > min_value:
          min = min_value
      return min
  
  
  input_num = input()
  input_list = []
  index_list = [1000, 2, 3, 5, 1000]
  for _ in range(int(input_num)):
      input_list.append(list(map(int, input().split(" "))))
  
  for item in input_list:
      search_root(item)
  
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)."}]