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: t = int(input())
  # スペース区切りの整数の入力
  for i in range(t):
      x = 0
      nn = 0
      n, a, b, c, d = map(int, input().split())
      if x == 0:
          x += 1
          nn += d
  
      while x != n:
          l = [
              abs(n - x * 2),
              abs(n - x * 3),
              abs(n - x * 5),
              min(abs(n - (x + 1)), abs(n - (x - 1))),
          ]
          # print(l)
          # print(x)
          # print(nn)
          min_indl = []
          mindL = 0
          flag = 0
          mins = abs(n - x * 2)
          for f in range(4):
              if mins > l[f]:
                  mins = l[f]
                  mindL = f
                  flag = 0
              elif mins == l[f]:
                  flag = 1
                  if mindL in min_indl:
                      min_indl.append(f)
                  else:
                      min_indl = [mindL, f]
  
          if flag == 0:
              if mindL == 0:
                  nn += a
                  x = x * 2
              elif mindL == 1:
                  nn += b
                  x = x * 3
              elif mindL == 2:
                  nn += c
                  x = x * 5
              elif mindL == 3:
                  nn += d
                  if abs(n - (x + 1)) < abs(n - (x - 1)):
                      x = x + 1
                  elif abs(n - (x + 1)) > abs(n - (x - 1)):
                      x = x - 1
                  else:
                      print("えらーC")
              else:
                  print("えらーA")
          elif flag == 1:
              cos = 0
              cosB = 0
              cosind = 0
              flagB = 0
              for j in min_indl:
  
                  if j == 0:
                      cos = a
                  elif j == 1:
                      cos = b
                  elif j == 2:
                      cos = c
                  elif j == 3:
                      cos = d
                  else:
                      print("えらーD")
                  if flag == 0:
                      flag += 1
                      cosB = cos
                      cosind = j
                  else:
                      if cosB > cos:
                          cosB = cos
                          cosind = j
              if cosind == 0:
                  nn += a
                  x = x * 2
              elif cosind == 1:
                  nn += b
                  x = x * 3
              elif cosind == 2:
                  nn += c
                  x = x * 5
              elif cosind == 3:
                  nn += d
                  if abs(n - x + 1) < abs(n - (x - 1)):
                      x = x + 1
                  elif abs(n - x + 1) > abs(n - (x - 1)):
                      x = x - 1
                  else:
                      print("えらーF")
  
          # print(x)
          # print(nn)
      print(nn)
  
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)."}]