output_description: Print N lines. The i-th line should contain the value f(X_i).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      X
attempt: #!/usr/bin/env python3
  
  import sys
  
  sys.setrecursionlimit(300000)
  
  
  def solve(N: int, X: str):
      memo = {}
  
      def popcount(v):
          if v == 0:
              return 0
          if v in memo:
              return memo[v]
          tmp, b = v, 0
          while tmp > 0:
              b += tmp % 2
              tmp //= 2
          if v % b == 0:
              memo[v] = 1
              return 1
          memo[v] = 1 + popcount(v % b)
          return memo[v]
  
      X = X[::-1]
      bits = 0
      for i in range(N):
          if X[i] == "1":
              bits += 1
  
      sums = [0, 0]
      for i in range(N):
          if X[i] == "1":
              sums[0] += pow(2, i, bits - 1)
              sums[0] %= bits - 1
              sums[1] += pow(2, i, bits + 1)
              sums[1] %= bits + 1
  
      # print(bits, sums)
      ret = []
      for i, x in enumerate(X):
          if x == "1":
              v = (sums[0] - (1 << i)) % (bits - 1)
          else:
              v = (sums[1] + (1 << i)) % (bits + 1)
          # print(i, x, v)
          ret.append(1 + popcount(v))
  
      ret.reverse()
      for r in ret:
          print(r)
      return
  
  
  def solve_(N: int, X: str):
      # memo = [[-1] * 20 for _ in range(20)]
      memo = {}
  
      def popcount(v, b):
          if v in memo and b in memo[v]:
              return memo[v][b]
          if not v in memo:
              memo[v] = {}
          if v % b == 0:
              memo[v][b] = 1
              return 1
          next_v = v % b
          tmp = next_v
          c = 0
          while tmp > 0:
              c += tmp % 2
              tmp //= 2
          ret = 1 + popcount(next_v, c)
          memo[v][b] = ret
          return ret
  
      X = X[::-1]
      count = 0
      for i in range(N):
          if X[i] == "1":
              count += 1
  
      s = 0
      for i in range(N):
          if X[i] == "1":
              s += pow(2, i, count)
              s %= count
  
      memo[count] = {}
      memo[count]
      ret = []
      for i, x in enumerate(X):
          if x == "1":
              v = N - (1 << i)
              b = count - 1
          else:
              v = N + (1 << i)
              b = count + 1
          print(i, i, x)
          print(v, b)
          ret.append(popcount(v, b))
      ret.reverse()
      for r in ret:
          print(r)
      return
  
  
  def main():
      def iterate_tokens():
          for line in sys.stdin:
              for word in line.split():
                  yield word
  
      tokens = iterate_tokens()
      N = int(next(tokens))  # type: int
      X = next(tokens)  # type: str
      solve(N, X)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  Let \mathrm{popcount}(n) be the number of `1`s in the binary representation of
  n. For example, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3, and
  \mathrm{popcount}(0) = 0.
  
  Let f(n) be the number of times the following operation will be done when we
  repeat it until n becomes 0: "replace n with the remainder when n is divided
  by \mathrm{popcount}(n)." (It can be proved that, under the constraints of
  this problem, n always becomes 0 after a finite number of operations.)
  
  For example, when n=7, it becomes 0 after two operations, as follows:
  
    * \mathrm{popcount}(7)=3, so we divide 7 by 3 and replace it with the remainder, 1.
    * \mathrm{popcount}(1)=1, so we divide 1 by 1 and replace it with the remainder, 0.
  
  You are given an integer X with N digits in binary. For each integer i such
  that 1 \leq i \leq N, let X_i be what X becomes when the i-th bit from the top
  is inverted. Find f(X_1), f(X_2), \ldots, f(X_N).
samples: [{"input": "3\n    011", "output": "2\n    1\n    1\n    \n\n  * X_1 = 7, which will change as follows: 7 \\rightarrow 1 \\rightarrow 0. Thus, f(7) = 2.\n  * X_2 = 1, which will change as follows: 1 \\rightarrow 0. Thus, f(1) = 1.\n  * X_3 = 2, which will change as follows: 2 \\rightarrow 0. Thus, f(2) = 1.\n\n* * *"}, {"input": "23\n    00110111001011011001110", "output": "2\n    1\n    2\n    2\n    1\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    2\n    1\n    3"}]