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: # 解説PDF読んで解説放送見てAC
  
  # 逆から操作を考える（終点のNから考える）
  # スカスカDP。なので配列を作らずに辞書で管理する必要がある
  
  import math
  
  
  def calc_cost(n, ans_dict):
  
      min_cost = n * d
  
      inc_2 = int(math.ceil(n / 2))
      if inc_2 not in ans_dict:
          ans_dict[inc_2] = calc_cost(inc_2, ans_dict)
      min_cost = min(min_cost, d * (inc_2 * 2 - n) + a + ans_dict[inc_2])
  
      dec_2 = int(math.floor(n / 2))
      if dec_2 not in ans_dict:
          ans_dict[dec_2] = calc_cost(dec_2, ans_dict)
      min_cost = min(min_cost, d * (-dec_2 * 2 + n) + a + ans_dict[dec_2])
  
      inc_3 = int(math.ceil(n / 3))
      if inc_3 not in ans_dict:
          ans_dict[inc_3] = calc_cost(inc_3, ans_dict)
      min_cost = min(min_cost, d * (inc_3 * 3 - n) + b + ans_dict[inc_3])
  
      dec_3 = int(math.floor(n / 3))
      if dec_3 not in ans_dict:
          ans_dict[dec_3] = calc_cost(dec_3, ans_dict)
      min_cost = min(min_cost, d * (-dec_3 * 3 + n) + b + ans_dict[dec_3])
  
      inc_5 = int(math.ceil(n / 5))
      if inc_5 not in ans_dict:
          ans_dict[inc_5] = calc_cost(inc_5, ans_dict)
      min_cost = min(min_cost, d * (inc_5 * 5 - n) + c + ans_dict[inc_5])
  
      dec_5 = int(math.floor(n / 5))
      if dec_5 not in ans_dict:
          ans_dict[dec_5] = calc_cost(dec_5, ans_dict)
      min_cost = min(min_cost, d * (-dec_5 * 5 + n) + c + ans_dict[dec_5])
  
      ans_dict[n] = min_cost
      return min_cost
  
  
  n_testcase = int(input())
  for i in range(n_testcase):
      n, a, b, c, d = list(map(int, input().split()))
  
      # テストケースごとに辞書はリセットしないとダメですね
      ans_dict = {}
  
      ans_dict[0] = 0
      ans_dict[1] = d  # 1減らすのが常に最善
  
      ans = calc_cost(n, ans_dict)
      print(ans)
      # print(ans_dict)
  
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)."}]