import sys

def I(): return int(sys.stdin.readline().rstrip())

def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし



N = I()



A = [0]  # A[i] = f(i) (0<=i<=N-1)

for i in range(1,N):

    a = 0  # iの2進表記に現れる1の個数

    for j in range(18):

        a += (i >> j) & 1

    A.append(1 + A[i % a])



X = LS2()



b = 0  # Xの2進表記に現れる1の個数

for i in range(N):

    if X[i] == '1':

        b += 1

if b >= 2:

    c1,c2 = b-1,b+1



    amari1 = [1]

    amari2 = [1]

    for i in range(1,N):

        amari1.append((amari1[-1]*2) % c1)

        amari2.append((amari2[-1]*2) % c2)

    amari1.reverse()

    amari2.reverse()



    # amari1[i] = 2**(N-i-1) mod c1

    # amari2[i] = 2**(N-i-1) mod c2



    r1,r2 = 0,0  # ri = X mod ci

    for i in range(N):

        if X[i] == '1':

            r1 += amari1[i]

            r1 %= c1

            r2 += amari2[i]

            r2 %= c2

    ANS = []

    for i in range(N):

        if X[i] == '1':

            ANS.append(A[(r1-amari1[i]) % c1]+1)

        else:

            ANS.append(A[(r2+amari2[i]) % c2]+1)

else:

    c2 = b+1



    amari2 = [1]

    for i in range(1, N):

        amari2.append((amari2[-1]*2) % c2)

    amari2.reverse()



    # amari2[i] = 2**(N-i-1) mod c2



    r2 = 0  # X mod c2

    for i in range(N):

        if X[i] == '1':

            r2 += amari2[i]

            r2 %= c2

    ANS = []

    for i in range(N):

        if X[i] == '1':

            ANS.append(0)

        else:

            ANS.append(A[(r2+amari2[i]) % c2] + 1)



print(*ANS,sep='\n')

import sys



sys.setrecursionlimit(10**7)

def I(): return int(sys.stdin.readline().rstrip())

def MI(): return map(int,sys.stdin.readline().rstrip().split())

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし

def S(): return sys.stdin.readline().rstrip()

def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり

def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし





N = I()

X = LI2()

X.reverse()



if N == 1 and len(X) == 1 and X[0] == 0:

    print(1)

    exit()





def popcount(n):

    res = 0

    m = n.bit_length()

    for i in range(m):

        res += (n >> i) & 1

    return res





F = [0]*(2*10**5)

for i in range(1,2*10**5):

    F[i] = 1 + F[i % popcount(i)]



a = sum(X)

b = a-1

c = a+1

if a == 1:

    A, C = [1], [1]  # 2冪をa,b,cで割った余り

    xa, xc = 0, 0  # Xをa,b,cで割った余り

    for i in range(N):

        if X[i] == 1:

            xa += A[-1]

            xc += C[-1]

            xa %= a

            xc %= c

        A.append((2 * A[-1]) % a)

        C.append((2 * C[-1]) % c)



    ANS = []

    for i in range(N):

        if X[i] == 1:

            ANS.append(0)

        else:

            ANS.append(1 + F[(xc + C[i]) % c])



    ANS.reverse()

    print(*ANS, sep='\n')

    exit()



A,B,C = [1],[1],[1]  # 2冪をa,b,cで割った余り

xa,xb,xc = 0,0,0  # Xをa,b,cで割った余り

for i in range(N):

    if X[i] == 1:

        xa += A[-1]

        xb += B[-1]

        xc += C[-1]

        xa %= a

        xb %= b

        xc %= c

    A.append((2*A[-1])%a)

    B.append((2*B[-1])%b)

    C.append((2*C[-1])%c)



ANS = []

for i in range(N):

    if X[i] == 1:

        ANS.append(1 + F[(xb-B[i]) % b])

    else:

        ANS.append(1 + F[(xc+C[i]) % c])



ANS.reverse()

print(*ANS,sep='\n')

import sys


def I():
    return int(sys.stdin.readline().rstrip())


def LS2():
    return list(sys.stdin.readline().rstrip())  # 空白なし


N = I()
A = [0]  # A[i] = f(i) (0<=i<=N-1)
for i in range(1, N):
    a = 0  # iの2進表記に現れる1の個数
    for j in range(18):
        a += (i >> j) & 1
    A.append(1 + A[i % a])
X = LS2()
b = 0  # Xの2進表記に現れる1の個数
for i in range(N):
    if X[i] == "1":
        b += 1
if b >= 2:
    c1, c2 = b - 1, b + 1
    amari1 = [1]
    amari2 = [1]
    for i in range(1, N):
        amari1.append((amari1[-1] * 2) % c1)
        amari2.append((amari2[-1] * 2) % c2)
    amari1.reverse()
    amari2.reverse()
    # amari1[i] = 2**(N-i-1) mod c1
    # amari2[i] = 2**(N-i-1) mod c2
    r1, r2 = 0, 0  # ri = X mod ci
    for i in range(N):
        if X[i] == "1":
            r1 += amari1[i]
            r1 %= c1
            r2 += amari2[i]
            r2 %= c2
    ANS = []
    for i in range(N):
        if X[i] == "1":
            ANS.append(A[(r1 - amari1[i]) % c1] + 1)
        else:
            ANS.append(A[(r2 + amari2[i]) % c2] + 1)
else:
    c2 = b + 1
    amari2 = [1]
    for i in range(1, N):
        amari2.append((amari2[-1] * 2) % c2)
    amari2.reverse()
    # amari2[i] = 2**(N-i-1) mod c2
    r2 = 0  # X mod c2
    for i in range(N):
        if X[i] == "1":
            r2 += amari2[i]
            r2 %= c2
    ANS = []
    for i in range(N):
        if X[i] == "1":
            ANS.append(0)
        else:
            ANS.append(A[(r2 + amari2[i]) % c2] + 1)
print(*ANS, sep="\n")

import sys

sys.setrecursionlimit(10**7)


def I():
    return int(sys.stdin.readline().rstrip())


def MI():
    return map(int, sys.stdin.readline().rstrip().split())


def LI():
    return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり


def LI2():
    return list(map(int, sys.stdin.readline().rstrip()))  # 空白なし


def S():
    return sys.stdin.readline().rstrip()


def LS():
    return list(sys.stdin.readline().rstrip().split())  # 空白あり


def LS2():
    return list(sys.stdin.readline().rstrip())  # 空白なし


N = I()
X = LI2()
X.reverse()
if N == 1 and len(X) == 1 and X[0] == 0:
    print(1)
    exit()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


F = [0] * (2 * 10**5)
for i in range(1, 2 * 10**5):
    F[i] = 1 + F[i % popcount(i)]
a = sum(X)
b = a - 1
c = a + 1
if a == 1:
    A, C = [1], [1]  # 2冪をa,b,cで割った余り
    xa, xc = 0, 0  # Xをa,b,cで割った余り
    for i in range(N):
        if X[i] == 1:
            xa += A[-1]
            xc += C[-1]
            xa %= a
            xc %= c
        A.append((2 * A[-1]) % a)
        C.append((2 * C[-1]) % c)
    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])
    ANS.reverse()
    print(*ANS, sep="\n")
    exit()
A, B, C = [1], [1], [1]  # 2冪をa,b,cで割った余り
xa, xb, xc = 0, 0, 0  # Xをa,b,cで割った余り
for i in range(N):
    if X[i] == 1:
        xa += A[-1]
        xb += B[-1]
        xc += C[-1]
        xa %= a
        xb %= b
        xc %= c
    A.append((2 * A[-1]) % a)
    B.append((2 * B[-1]) % b)
    C.append((2 * C[-1]) % c)
ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb - B[i]) % b])
    else:
        ANS.append(1 + F[(xc + C[i]) % c])
ANS.reverse()
print(*ANS, sep="\n")

+ +sys.setrecursionlimit(10**7) + + +def MI(): +    return map(int, sys.stdin.readline().rstrip().split()) + + +def LI(): +    return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり + + +def LI2(): +    return list(map(int, sys.stdin.readline().rstrip()))  # 空白なし + + +def S(): +    return sys.stdin.readline().rstrip() + + +def LS(): +    return list(sys.stdin.readline().rstrip().split())  # 空白あり -A = [0]  # A[i] = f(i) (0<=i<=N-1) -for i in range(1, N): -    a = 0  # iの2進表記に現れる1の個数 -    for j in range(18): -        a += (i >> j) & 1 -    A.append(1 + A[i % a]) -X = LS2() -b = 0  # Xの2進表記に現れる1の個数 -for i in range(N): -    if X[i] == "1": -        b += 1 -if b >= 2: -    c1, c2 = b - 1, b + 1 -    amari1 = [1] -    amari2 = [1] -    for i in range(1, N): -        amari1.append((amari1[-1] * 2) % c1) -        amari2.append((amari2[-1] * 2) % c2) -    amari1.reverse() -    amari2.reverse() -    # amari1[i] = 2**(N-i-1) mod c1 -    # amari2[i] = 2**(N-i-1) mod c2 -    r1, r2 = 0, 0  # ri = X mod ci +X = LI2() +X.reverse() +if N == 1 and len(X) == 1 and X[0] == 0: +    print(1) +    exit() + + +def popcount(n): +    res = 0 +    m = n.bit_length() +    for i in range(m): +        res += (n >> i) & 1 +    return res + + +F = [0] * (2 * 10**5) +for i in range(1, 2 * 10**5): +    F[i] = 1 + F[i % popcount(i)] +a = sum(X) +b = a - 1 +c = a + 1 +if a == 1: +    A, C = [1], [1]  # 2冪をa,b,cで割った余り +    xa, xc = 0, 0  # Xをa,b,cで割った余り -        if X[i] == "1": -            r1 += amari1[i] -            r1 %= c1 -            r2 += amari2[i] -            r2 %= c2 +        if X[i] == 1: +            xa += A[-1] +            xc += C[-1] +            xa %= a +            xc %= c +        A.append((2 * A[-1]) % a) +        C.append((2 * C[-1]) % c) -        if X[i] == "1": -            ANS.append(A[(r1 - amari1[i]) % c1] + 1) -        else: -            ANS.append(A[(r2 + amari2[i]) % c2] + 1) -else: -    c2 = b + 1 -    amari2 = [1] -    for i in range(1, N): -        amari2.append((amari2[-1] * 2) % c2) -    amari2.reverse() -    # amari2[i] = 2**(N-i-1) mod c2 -    r2 = 0  # X mod c2 -    for i in range(N): -        if X[i] == "1": -            r2 += amari2[i] -            r2 %= c2 -    ANS = [] -    for i in range(N): -        if X[i] == "1": +        if X[i] == 1: -            ANS.append(A[(r2 + amari2[i]) % c2] + 1) +            ANS.append(1 + F[(xc + C[i]) % c]) +    ANS.reverse() +    print(*ANS, sep="\n") +    exit() +A, B, C = [1], [1], [1]  # 2冪をa,b,cで割った余り +xa, xb, xc = 0, 0, 0  # Xをa,b,cで割った余り +for i in range(N): +    if X[i] == 1: +        xa += A[-1] +        xb += B[-1] +        xc += C[-1] +        xa %= a +        xb %= b +        xc %= c +    A.append((2 * A[-1]) % a) +    B.append((2 * B[-1]) % b) +    C.append((2 * C[-1]) % c) +ANS = [] +for i in range(N): +    if X[i] == 1: +        ANS.append(1 + F[(xb - B[i]) % b]) +    else: +        ANS.append(1 + F[(xc + C[i]) % c]) +ANS.reverse()