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: import sys
  from functools import lru_cache
  
  sys.setrecursionlimit(10**6)
  
  
  def main():
      T = int(input())
      TESTCASEs = [list(map(int, input().split())) for _ in range(T)]
  
      def calc_cost(N, A, B, C, D):
  
          @lru_cache(maxsize=None)
          def calc(N):
              if N == 0:
                  return 0
              if N == 1:
                  return D
  
              cost = N * D
  
              for T, Tcost in ((2, A), (3, B), (5, C)):
                  div, mod = divmod(N, T)
  
                  cost = min(cost, calc(div) + Tcost + mod * D)
                  if mod:
                      cost = min(cost, calc(div + 1) + Tcost + (T - mod) * D)
  
              return cost
  
          return calc(N)
  
      for TESTCASE in TESTCASEs:
          total_cost = calc_cost(*TESTCASE)
          print(total_cost)
  
  
  if __name__ == "__main__":
      main()
  
  sys.exit()
  
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)."}]