output_description: Print T lines. The i-th line should contain the answer to the i-th test case.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      T
      \mathrm{case}_1
      \vdots
      \mathrm{case}_T
      
  
  Each case is given in the following format:
  
      
      
      N
      K_1 L_1 R_1
      \vdots
      K_N L_N R_N
attempt: n = int(input())
  x = list(input())
  cnt = x.count("1")
  
  
  def popcount(x):
      """xの立っているビット数をカウントする関数
      (xは64bit整数)"""
  
      # 2bitごとの組に分け、立っているビット数を2bitで表現する
      x = x - ((x >> 1) & 0x5555555555555555)
  
      # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
      x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  
      x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F  # 8bitごと
      x = x + (x >> 8)  # 16bitごと
      x = x + (x >> 16)  # 32bitごと
      x = x + (x >> 32)  # 64bitごと = 全部の合計
      return x & 0x0000007F
  
  
  for i in range(n):
      y = x[:]
      if x[i] == "1":
          y[i] = "0"
          z = "".join(y)
          z = int(z, 2)
          z %= cnt - 1
          if z == 0:
              print(1)
          else:
              ans = 1
              while z > 0:
                  z %= popcount(z)
                  ans += 1
              print(ans)
      else:
          y[i] = "1"
          z = "".join(y)
          z = int(z, 2)
          z %= cnt + 1
          if z == 0:
              print(1)
          else:
              ans = 1
              while z > 0:
                  z %= popcount(z)
                  ans += 1
              print(ans)
  
problem_description: Statement
  
  We have N camels numbered 1,2,\ldots,N. Snuke has decided to make them line up
  in a row.
  
  The happiness of Camel i will be L_i if it is among the K_i frontmost camels,
  and R_i otherwise.
  
  Snuke wants to maximize the total happiness of the camels. Find the maximum
  possible total happiness of the camel.
  
  Solve this problem for each of the T test cases given.
samples: [{"input": "3\n    2\n    1 5 10\n    2 15 5\n    3\n    2 93 78\n    1 71 59\n    3 57 96\n    19\n    19 23 16\n    5 90 13\n    12 85 70\n    19 67 78\n    12 16 60\n    18 48 28\n    5 4 24\n    12 97 97\n    4 57 87\n    19 91 74\n    18 100 76\n    7 86 46\n    9 100 57\n    3 76 73\n    6 84 93\n    1 6 84\n    11 75 94\n    19 15 3\n    12 11 34", "output": "25\n    221\n    1354\n    \n\n  * In the first test case, it is optimal to line up the camels in the order 2, 1.\n    * Camel 1 is not the frontmost camel, so its happiness will be 10.\n    * Camel 2 is among the two frontmost camels, so its happiness will be 15.\n  * In the second test case, it is optimal to line up the camels in the order 2, 1, 3.\n    * Camel 1 is among the two frontmost camels, so its happiness will be 93.\n    * Camel 2 is the frontmost camel, so its happiness will be 71.\n    * Camel 3 is among the three frontmost camels, so its happiness will be 57."}]