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: from heapq import heapify, heappop, heappush, heappushpop
  
  
  class PriorityQueue:
      def __init__(self, heap=None):
          """
          heap ... list
          """
          self.heap = heap or []
          heapify(self.heap)
  
      def push(self, item):
          heappush(self.heap, item)
  
      def pop(self):
          return heappop(self.heap)
  
      def pushpop(self, item):
          return heappushpop(self.heap, item)
  
      def __call__(self):
          return self.heap
  
      def __len__(self):
          return len(self.heap)
  
  
  def solve(N, A, B, C, D):
      pq = PriorityQueue()
      visited = dict()
  
      best = 2**63
      pq.push((0, N))
  
      while len(pq) > 0:
          cost, now = pq.pop()
          if now < 0:
              continue
          if now in visited and visited[now] <= cost:
              continue
          visited[now] = cost
  
          # debug("cost %lld, now %lld, [%d]\n", cost, now, last);
          if now == 0:
              best = min(best, cost)
  
          for d in range(-4, 5):
              x = now + d
              c = cost + D * abs(d)
              if x == 0:
                  best = min(best, c)
              if x % 5 == 0:
                  minc = min(C, D * (x - x // 5))
                  pq.push((c + minc, x // 5))
  
          for d in range(-2, 3):
              x = now + d
              c = cost + D * abs(d)
              if x == 0:
                  best = min(best, c)
              if x % 3 == 0:
                  minc = min(B, D * (x - x // 3))
                  pq.push((c + minc, x // 3))
  
          for d in range(-1, 2):
              x = now + d
              c = cost + D * abs(d)
              if x == 0:
                  best = min(best, c)
              if x % 2 == 0:
                  minc = min(A, D * (x - x // 2))
                  pq.push((c + minc, x // 2))
  
      return best
  
  
  if __name__ == "__main__":
      T = int(input())
      for t in range(T):
          N, A, B, C, D = map(int, input().split(" "))
          print(solve(N, A, B, C, D))
  
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)."}]