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: """
  A枚のコインを支払い、持っている数を 2倍する。
  B枚のコインを支払い、持っている数を 3倍する。
  C枚のコインを支払い、持っている数を 5倍する。
  D枚のコインを支払い、持っている数を 1増やす、または 1減らす。
  持っている数をNとするには、最小で何枚のコインが必要でしょうか。
  """
  
  N, A, B, C, D = map(int, input().split())
  arr = [0] * N
  arr[0] = D
  
  arr[1] = min(2 * D, D + A)
  arr[2] = min(3 * D, D + B, 2 * D + A)
  arr[3] = min(4 * D, D + 2 * A, 2 * D + B, 2 * D + C)
  arr[4] = min(5 * D, 2 * D + 2 * A, A + B + 2 * D, D + C)
  
  for i in range(5, N, 1):
      arr[i] = min(
          arr[((i + 1) // 2) + 1] + A + D * abs(i + 1 - (2 * ((i + 1) // 2))),
          arr[((i + 1) // 2) + 2] + A + D * abs(i + 1 - (2 * (((i + 1) // 2)) + 1)),
          arr[((i + 1) // 3) + 1] + B + D * abs(i + 1 - (3 * ((i + 1) // 3))),
          arr[((i + 1) // 3) + 2] + B + D * abs(i + 1 - (3 * (((i + 1) // 3)) + 1)),
          arr[((i + 1) // 5) + 1] + C + D * abs(i + 1 - (5 * ((i + 1) // 5))),
          arr[((i + 1) // 5) + 2] + C + D * abs(i + 1 - (5 * (((i + 1) // 5)) + 1)),
      )
  
  print(arr[-1])
  
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)."}]