Buggy python submission (verdict: Runtime Error):
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        x1 += memo1[i]
        x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Runtime Error):
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = bin(x).count("1")

for i in range(n):
    y = 0
    py = px
    if x & (1 << i):
        y = x - 2 ** i
        py -= 1
    else:
        y= x + 2 ** i
        py += 1
    ans.append(solve(y%py)+1)

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Runtime Error):
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = bin(x).count("1")

for i in range(n):
    y = 0
    py = px
    if x & (1 << i):
        y = x - 2 ** i
        py -= 1
    else:
        y= x + 2 ** i
        py += 1
    ans.append(solve(y%py)+1)

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x - 2 ** i
    else:
        y= x + 2 ** i
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

n = int(input())
x = eval('0b' + input())

memo = {0: 0}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % bin(x).count("1"), cnt + 1)
        memo[x] = ans - cnt
        return ans


ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % bin(x).count("1"), cnt + 1)
        memo[x] = ans - cnt
        return ans


ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

def popcount(x):
    res = 0
    for i in range(x.bit_length()+1):
        if x & (1 << i):
            res += 1 
    return res

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % popcount(x), cnt + 1)
        memo[x] = ans - cnt
        return ans


px = popcount(x)
ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

def popcount(x):
    res = 0
    for i in range(n+1):
        if x & (1 << i):
            res += 1 
    return res

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % popcount(x), cnt + 1)
        memo[x] = ans - cnt
        return ans


px = popcount(x)
ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
x = eval('0b' + input())

def popcount(x):
    res = 0
    for i in range(n+1):
        if x & (1 << i):
            res += 1 
    return res

memo = {}

# def slove(x):
#     cnt = 0
#     tmp = []
#     while x:
#         if x in memo:
#             return cnt + memo[x]
#         else:

#         x = x % popcount(x)
#         cnt += 1
#     return cnt

def solve(x, cnt):
    if x == 0:
        return cnt

    if x in memo:
        return cnt + memo[x]
    else:
        ans = solve(x % popcount(x), cnt + 1)
        memo[x] = ans - cnt
        return ans


px = popcount(x)
ans = []

for i in range(n):
    y = 0
    if x & (1 << i):
        y = x & ~(1 << i)
    else:
        y= x | (1 << i)
    ans.append(solve(y, 0))

for ansi in reversed(ans):
    print(ansi)


    

        


Fixed submission:
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)