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 loopi in range(t):
      n, a, b, c, d = list(map(int, input().split()))
      minest = 10**40
      dd = {n: 0}
      while 1:
          newd = {}
          for i in dd:
              if i % 2:
                  l = int((i - 1) / 2)
                  if l in newd:
                      newd[l] = min(dd[i] + min(a + d, (i - l) * d), newd[l])
                  else:
                      newd[l] = dd[i] + min(a + d, (i - l) * d)
                  l = int((i + 1) / 2)
                  if l in newd:
                      newd[l] = min(dd[i] + min(a + d, (i - l) * d), newd[l])
                  else:
                      newd[l] = dd[i] + min(a + d, (i - l) * d)
              else:
                  l = int(i / 2)
                  if l in newd:
                      newd[l] = min(dd[i] + min(a, l * d), newd[l])
                  else:
                      newd[l] = dd[i] + min(a, l * d)
              l = int((i - (i + 1) % 3 + 1) / 3)
              if l in newd:
                  newd[l] = min(
                      dd[i] + min(d * ((i + 1) % 3 - 1) ** 2 + b, (i - l) * d), newd[l]
                  )
              else:
                  newd[l] = dd[i] + min(d * ((i + 1) % 3 - 1) ** 2 + b, (i - l) * d)
              l = int((i - (i + 2) % 5 + 2) / 5)
              if l in newd:
                  newd[l] = min(
                      dd[i]
                      + min(d * int((((i + 2) % 5 - 2) ** 2) ** 0.5) + c, (i - l) * d),
                      newd[l],
                  )
              else:
                  newd[l] = dd[i] + min(
                      d * int((((i + 2) % 5 - 2) ** 2) ** 0.5) + c, (i - l) * d
                  )
          if 1 in newd:
              mmm = newd.pop(1)
              if minest > mmm:
                  minest = mmm
          if 0 in newd:
              newd.pop(0)
          if len(newd) == 0:
              break
          dd = newd
      print(minest + 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)."}]