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 heapq
  
  
  def calc(n, a, b, c, d):
      candidates = []
      cost = {2: a, 3: b, 5: c}
      que = [(0, n)]
      heapq.heapify(que)
      mult = [2, 3, 5]
      ans = 10**18
      while len(que) > 0:
          c, v = heapq.heappop(que)
          if ans < c:
              break
          for m in mult:
              if v < m:
                  print(*que)
                  t = c + d * v
                  candidates.append(t)
                  ans = min(ans, t)
  
              c1 = d * (v - (v // m * m)) + cost[m] + c
              v1 = v // m
              c2 = -d * (v + (-v) // m * m) + cost[m] + c
              v2 = -(-v // m)
              if c1 < c2:
                  heapq.heappush(que, (c1, v1))
              else:
                  heapq.heappush(que, (c2, v2))
          # for value,cost in stack:
          #     for m in mult:
          #         if value<m:
          #             candidates.append(cost+d*value)
          #             continue
          #         c1 = d*(value-(value//m*m)) + c[m] + cost
          #         v1 = value//m
          #         c2 = -d*(value+(-value)//m*m) + c[m] + cost
          #         v2 = -(-value//m)
  
      print(min(candidates))
  
  
  def main():
      calc(*tuple(map(int, input().split())))
      # t = int(input())
  
      # for _ in range(t):
      #     n,a,b,c,d = tuple(map(int,input().split()))
      #     print(calc(n,a,b,c,d))
  
  
  if __name__ == "__main__":
      main()
  
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)."}]