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).
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    X = int(readline().strip(), 2)


    def count(x):
        cnt = 0
        while x:
            x %= bin(x).count("1")
            cnt += 1
        return cnt
        
    ans = []
    for i in range(N):
        tmp = X ^ (1 << i)
        ans.append(count(tmp))

    print(ans[::-1])


if __name__ == "__main__":
    main()

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    X_bin = readline().strip()
    n = X_bin.count("1")
    X = int(X_bin, 2)

    X_pop_p = X % (n + 1)
    if n != 1:
        X_pop_m = X % (n - 1)

    
    def count(x):
        cnt = 1
        while x:
            x %= bin(x).count("1")
            cnt += 1
        return cnt
        
    ans = []
    for i in range(N):
        X_i = X ^ (1 << i)
        if X_i == 0:
            ans.append(0)
        else:
            if X_bin[-(i+1)] == "1":
                mod = (X_pop_m - pow(2, i, n - 1)) % (n - 1)
                ans.append(count(mod))
            else:
                mod = (X_pop_p + pow(2, i, n + 1)) % (n + 1)
                ans.append(count(mod))

    print("\n".join(map(str, ans[::-1])))


if __name__ == "__main__":
    main()
