Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#memo = [-1] * (N+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        pop = popcount(k)
        #key = k
        cnt = 1
        while k > 0:
            #print('  ', k, pop, cnt)
            #if memo[key] > 0:
            #    cnt += memo[k]
            #    break
            #else:
            k %= pop
            pop = popcount(k)
            cnt += 1
        #memo[key] = cnt
        print(cnt)


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#memo = [-1] * (N+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        pop = popcount(k)
        #key = k
        cnt = 1
        while k > 0:
            #print('  ', k, pop, cnt)
            #if memo[key] > 0:
            #    cnt += memo[k]
            #    break
            #else:
            k %= pop
            pop = popcount(k)
            cnt += 1
        #memo[key] = cnt
        print(cnt)


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T

    if pop == 0:
        print(0)
    else:
        ans = 1
        #print('  ', k, pop, ans)
        k %= pop
        pop = popcount(k)
        while k > 0:
            k %= pop
            pop = popcount(k)
            ans += 1
            #print('  ', k, pop, ans)
        print(ans)
        T //= 2

Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    k %= pop

    if pop == 0:
        print(0)
    else:
        ans = 1
        #print('  ', k, pop, ans)
        pop = popcount(k)
        while k > 0:
            k %= pop
            pop = popcount(k)
            ans += 1
            #print('  ', k, pop, ans)
        print(ans)
        T //= 2


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
K_MOD   = K % one
K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    k %= pop

    if pop == 0:
        print(0)
    else:
        ans = 1
        while k != 0:
            pop = popcount(k)
            k %= pop
            ans += 1
        print(ans)
        T //= 2

Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = input()

d = {}
def popcount(s):
    if not s in d:
        d[s] = s.count('1')
    return d[s]

one = popcount(X)
K = int(X, 2)
T = 2**(N-1)
for i in range(N):
    pop = one
    k = K
    if X[i] == '1':
        pop -= 1
        k -= T
    else:
        pop += 1
        k += T

    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
    print(ans)
    T //= 2


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = input()

d = {}
def popcount(s):
    if not s in d:
        d[s] = s.count('1')
    return d[s]

one = popcount(X)
K = int(X, 2)
for i in range(N):
    pop = one
    if X[i] == '1':
        pop -= 1
    else:
        pop += 1

    k = K
    bit = N-i-1
    if X[i] == '1':
        k -= 2**bit
    else:
        k += 2**bit
    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
    print(ans)


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = input()

d = {}
def popcount(s):
    if not s in d:
        cnt = 0
        for c in s:
            if c == '1':
                cnt += 1
        d[s] = cnt
    return d[s]

one = popcount(X)
K = int(X, 2)
for i in range(N):
    pop = one
    if X[i] == '1':
        pop -= 1
    else:
        pop += 1

    k = K
    bit = N-i-1
    if X[i] == '1':
        k -= 2**bit
    else:
        k += 2**bit
    #print(X[i], pop, k)
    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
        #print('  ', bin(k), pop, ans)
    print(ans)


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = input()

d = {}
def popcount(s):
    if not s in d:
        cnt = 0
        for c in s:
            if c == '1':
                cnt += 1
        d[s] = cnt
    return d[s]

one = popcount(X)
for i in range(N):
    pop = one
    if X[i] == '1':
        pop -= 1
    else:
        pop += 1

    k = int(X, 2)
    bit = N-i-1
    if X[i] == '1':
        k -= 2**bit
    else:
        k += 2**bit
    #print(X[i], pop, k)
    ans = 0
    while k > 0:
        k %= pop
        pop = popcount(bin(k)[2:])
        ans += 1
        #print('  ', bin(k), pop, ans)
    print(ans)


Fixed submission:
N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)