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: class coinManager:
      haveNum = 0
      spentCoin = 0
      target = 0
      costA = 0
      costB = 0
      costC = 0
      cosdD = 0
  
      minCost = ""
  
      def __init__(self, target: int, A: int, B: int, C: int, D: int):
          self.target = target
          self.costA = A
          self.costB = B
          self.costC = C
          self.costD = D
  
          self.setMinCost()
  
      def setMinCost(self):
          if self.costA * 1.5 <= self.costB and self.costA * 5 / 2 <= self.costC:
              self.minCost = "A"
          elif self.costA * 1.5 >= self.costB and self.costB * 5 / 3 <= self.costC:
              self.minCost = "B"
          elif self.costA * 5 / 2 >= self.costC and self.costB * 5 / 3 >= self.costC:
              self.minCost = "B"
          else:
              print("NNNNNNNNNNNNNNNNNNNNNNN")
  
          print(self.minCost)
  
      def checkTargetAndHaveNum(self) -> bool:
          return True if self.target == self.haveNum else False
  
      def remainNum(self) -> int:
          return self.target - self.haveNum
  
      def printCoin(self):
          print("-----Coin-----")
          print("target  = ", self.target)
          print("haveNum = ", self.haveNum)
          print("remain  = ", self.remainNum())
          print()
  
      def firstStep(self):
          self.spentD_increment()
          self.printCoin()
  
      def spentA(self):
          self.haveNum *= 2
          self.spentCoin += self.costA
  
      def spentB(self):
          self.haveNum *= 3
          self.spentCoin += self.costB
  
      def spentC(self):
          self.haveNum *= 5
          self.spentCoin += self.costC
  
      def spentD_increment(self):
          self.haveNum += 1
          self.spentCoin += self.costD
  
      def spentD_decrement(self):
          self.haveNum -= 1
          self.spentCoin += self.costD
  
  
  T = int(input())
  
  Input = []
  
  for _ in range(T):
      line = list(map(int, input().split()))
      Input.append(line)
  
  result = []
  
  
  for line in Input:
      coins = coinManager(*line)
      coins.printCoin()
  
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)."}]