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 q in range(0, t):
      z = input()
      z0 = z.split()
      n = int(z0[0])
      a = int(z0[1])
      b = int(z0[2])
      c = int(z0[3])
      d = int(z0[4])
      ai = 0
      aj0 = 0
      bj0 = 0
      cj0 = 0
      y4 = 0
      while 2**ai < 4 * n / 3:
          bi = 0
          while 3**bi < 4 * n / 3:
              ci = 0
              while 5**ci < 4 * n / 3:
                  if abs((2**ai) * (3**bi) * (5**ci) - n) < 2 * n / 3:
                      y = abs((2**ai) * (3**bi) * (5**ci) - n)
                      y1 = (
                          ai * a
                          + bi * b
                          + ci * c
                          + (abs((2**ai) * (3**bi) * (5**ci) - n) + 1) * d
                      )
                      for i in range(0, y + 1):
                          k = 0
                          for l in range(0, i + 1):
                              for aj in range(0, ai):
                                  for bj in range(0, bi):
                                      for cj in range(0, ci):
                                          k = k + (2 * aj + 3 * bj * 5 * cj)
                          y2 = (
                              ai * a
                              + bi * b
                              + ci * c
                              + (abs((2**ai) * (3**bi) * (5**ci) + k - n) + 1) * d
                          )
                          if y1 > y2:
                              y1 = y2
                      y3 = y1
                      if y3 < y4 or y4 == 0:
                          y4 = y3
                  ci = ci + 1
              bi = bi + 1
          ai = ai + 1
      print(y4)
  
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)."}]