Problem:
 Score : 400 points    Problem 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) .      Constraints  1 \leq N \leq 2 \times 10^5  X is an integer with N digits in binary, possibly with leading zeros.         Input Input is given from Standard Input in the following format:  N  X       Output Print N lines. The i -th line should contain the value f(X_i) .        Sample Input 1 3
011      Sample Output 1 2
1
1   X_1 = 7 , which will change as follows: 7 \rightarrow 1 \rightarrow 0 . Thus, f(7) = 2 .  X_2 = 1 , which will change as follows: 1 \rightarrow 0 . Thus, f(1) = 1 .  X_3 = 2 , which will change as follows: 2 \rightarrow 0 . Thus, f(2) = 1 .        Sample Input 2 23
00110111001011011001110      Sample Output 2 2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3

Solution (Python):
import sys





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


def main():
	n=II()

	a=[0]*(2*10**5+100)
	for i in range(1,2*10**5+50):
		b=bin(i).count("1")
		a[i]=a[i%b]+1
	

	s=input()
	c=s.count("1")
	

	if c==1:
		ans=[]
		for i,ss in enumerate(reversed(s)):
			if ss=="1":
				ans.append(0)
			else:
				if s[-1]=="1" or i==0:
					ans.append(2)
				else:
					ans.append(1)

		for i in reversed(ans):
			print(i)
		exit()


	p=c+1
	n=c-1
	pp=0
	nn=0

	for i,ss in enumerate(reversed(s)):
		
		if ss=="1":
			pp+=pow(2,i,p)
			nn+=pow(2,i,n)
			pp%=p
			nn%=n


	ans=[]

	for i,ss in enumerate(reversed(s)):
		if ss=="0":
			k=pp+pow(2,i,p)%p
			k%=p
			ans.append(a[k]+1)
		else:
			k=nn-pow(2,i,n)%n
			k%=n
			ans.append(a[k]+1)

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






if __name__ == "__main__":
	main()

Solution (Python):
from collections import defaultdict

N = int(input())
X = input()[::-1]


def popcount(n):
    p = 0
    while n > 0:
        p += n & 1
        n >>= 1
    return p


f = defaultdict(int)
for i in range(1, N + 1):
    f[i] = f[i % popcount(i)] + 1

P = X.count('1')
base = dict()
R = defaultdict(int)
for r in [P - 1, P + 1]:
    if r == 0:
        continue
    base[r] = [1] * N
    for i in range(1, N):
        base[r][i] = base[r][i - 1] * 2 % r
    R[r] = sum(base[r][i] * int(X[i]) for i in range(N)) % r

ans = [0] * N
for i in range(N):
    if X[i] == '1' and P == 1:
        ans[i] = 0
        continue
    if X[i] == '0':
        r = P + 1
        res = R[r] + base[r][i]
    else:
        r = P - 1
        res = R[r] - base[r][i]
    ans[i] = f[res % r] + 1

for i in range(N):
    print(ans[N - i - 1])

Solution (Python):
arr=[0,1,1,2]
n=4*(10**5)+100
for i in range(4,n):
    b=bin(i)[2:]
    k=b.count('1')
    arr.append(arr[i%k]+1)
    
n=int(input())
z=input()
l=z.count('1')
l1=l+1
l2=l-1
ans1=0
ans2=0
for i in range(n):
    if(z[i]=='1'):
        u=pow(2,n-1-i,l1)
        ans1=(ans1+u)%l1
        if l2>0:
            ans2=(ans2+pow(2,n-1-i,l2))%l2
for i in range(n):
    if z[i]=='0':
        p=ans1+pow(2,n-1-i,l1)
        p%=l1
        print(1+arr[p])
    else:
        if l2==0:
            print(0)
        else:
            p=ans2-pow(2,n-1-i,l2)
            p%=l2
            print(1+arr[p])

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
x=input()
m=int(x,2)
c=x.count("1")
l=[1]*(2*10**5+2)
for i in range(1,2*10**5+1):
    l[i]=l[i%str(bin(i)).count("1")]+1
deka=0
for i in range(n):
    if x[i]=="1":
        deka+=pow(2,n-i-1,c+1)
        deka%=c+1
tiisa=0
if c!=1:
    for i in range(n):
        if x[i]=="1":
            tiisa+=pow(2,n-i-1,c-1)
            tiisa%=c-1

for i in range(n):
    if x[i]=="0":
        nex=(deka+pow(2,n-i-1,c+1))%(c+1)
    else:
        if c-1==0:
            nex=-1
        else:
            nex=(tiisa-pow(2,n-i-1,c-1))%(c-1)
    if nex==0:
        print(1)
    elif nex==-1:
        print(0)
    else:
        print(l[nex])

Solution (Python):
import sys
input = sys.stdin.readline
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def f(y):
    cnt  = 0
    tmp = y
    while tmp:
        tmp = tmp%popcnt(tmp)
        cnt += 1
    return cnt

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

cc = 0
for e in x:
    if e == '1':
        cc += 1

if cc == 0:
    for i in range(n):
        print(1)
    exit()
if cc == 1:
    p = 1
    q = 1
    
    s = 0
    
    t = 0

    for i in range(n-1,-1,-1):
        if x[i] == '1':
            s = (s+p)%(cc+1)
        p = p*2%(cc+1)




    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((s+pow(2,n-1-i,cc+1))%(cc+1))+1)
        
    exit()


p = 1
q = 1

s = 0

t = 0

for i in range(n-1,-1,-1):
    if x[i] == '1':
        s = (s+p)%(cc+1)
        t = (t+q)%(cc-1)
    p = p*2%(cc+1)
    q = q*2%(cc-1)



for i in range(n):
    if x[i] == '1':
        print(f((t-pow(2,n-1-i,cc-1))%(cc-1))+1)
    else:
        print(f((s+pow(2,n-1-i,cc+1))%(cc+1))+1)

Solution (Python):
N=int(input())
X=input()

k=0
for i in range(N):
  if X[i]=="1":
    k+=1

A=int(X,2)

ap=A%(k+1)

am=100
if k != 1:
  am=A%(k-1)

popc_list=[-1]*(k+3)

def F(num):
  
  if num==0:
    return 0
  if popc_list[num]!=-1:
    return popc_list[num]
  
  popc=0
  for s in bin(num):
    if s == "1":
      popc+=1
      
  popc_list[num]=F(num%popc)+1
  return popc_list[num]
  

for i in range(N):
  if X[i] == "0":
    print(F((ap+pow(2,N-1-i,k+1))%(k+1))+1)
  else:
    if k == 1:
      print(0)
      continue
    print(F((am-pow(2,N-1-i,k-1))%(k-1))+1)
"""
print(popc_list)
print(k)
"""

Solution (Python):
import sys
from collections import defaultdict, deque, Counter
import math

from bisect import bisect_left, bisect_right





input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def solve(n):
    ans = 0
    while(n > 0):
        tmp = n
        pc = 0
        
        while(tmp > 0):
            if tmp % 2 == 1:
                pc += 1
            tmp //= 2
        n = n % pc
        ans += 1

    return ans



def main():
    n = getN()
    S = getS()
    N = int(S, 2)
    yobi = []

    for i in range(0, 200200):
        ret = solve(i)
        yobi.append(ret)
    

    tmp = N
    pc = 0
    
    pc = Counter(S)["1"]

    start1 = N % (pc + 1)
    rui1 = [1 % (pc + 1)]
    for i in range(n + 2):
        rui1.append((rui1[-1] * 2) % (pc + 1))
    if pc > 1:
        start2 = N % (pc - 1)
        rui2 = [1 % (pc - 1)]
        for i in range(n+2):
            rui2.append((rui2[-1] * 2) % (pc - 1))

    
    
    
    for i, c in enumerate(S):
        if c == "0":
            nx = (start1 + rui1[n - i - 1]) % (pc + 1)
            print(yobi[nx] + 1)
        if c == "1":
            if pc == 1:
                print(0)
            else:
                nx = (start2 - rui2[n - i - 1]) % (pc - 1)
                print(yobi[nx] + 1)

    

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq

import bisect
import sys

sys.setrecursionlimit(10**6)


def bfs(s, n, node):
    
    check = [False for _ in range(n)]
    check[s] = True
    
    queue = deque([s])
    visited_num = 1

    
    
    color = [-1 for _ in range(n)]
    color[s] = 0

    while visited_num < n:
        
        if len(queue) == 0:
            
            
            return color

        now_vertex = queue.popleft()
        
        for next_vertex in node[now_vertex]:

            if check[next_vertex] == True:
                continue

            queue.append(next_vertex)
            check[next_vertex] = True

            
            color[next_vertex] = color[now_vertex]+1
            visited_num += 1

    return color


mod = 10**9+7



def ceil(x, y): return (x+y-1)//y
def input_list(): return list(map(int, input().split()))


n = int(input())
tmp = input()

x = int(tmp, 2)
bit_num = tmp.count("1")

p_bit = x % (bit_num+1)
m_bit_flg = False
if bit_num < 2:
    m_bit_flg = True
else:
    m_bit = x % (bit_num-1)

for i in range(n):
    if tmp[i] == "0":
        cal = (p_bit+pow(2, n-i-1, bit_num+1)) % (bit_num+1)
    else:
        if m_bit_flg:
            print(0)
            continue
        cal = (m_bit-pow(2, n-i-1, bit_num-1)) % (bit_num-1)
    ans = 1
    while(cal > 0):
        cal = cal % bin(cal).count("1")
        ans += 1
    
    
    print(ans)

Solution (Python):
N = int(input())
X = input()
p0 = X.count('1')
p1, p2 = p0-1, p0+1
mem = {0:0}
def f(n):
    if n in mem:
        return mem[n]
    else:
        p = bin(n).count('1')
        ret = f(n % p) + 1
        mem[n] = ret
        return ret
r1 = r2 = 0
k1 = k2 = 1
for i in range(N):
    if X[-i-1] == '1':
        if p1 > 0:
            r1 = (r1+k1) % p1
        r2 = (r2+k2) % p2
    if p1 > 0:
        k1 = k1 * 2 % p1
    k2 = k2 * 2 % p2

ans = [None]*N
k1 = k2 = 1
for i in range(N):
    if X[-i-1] == '0':
        r = (r2 + k2) % p2
        ans[-i-1] = f(r) + 1
    elif p1 > 0:
        r = (r1 - k1) % p1
        ans[-i-1] = f(r) + 1
    else:
        ans[-i-1] = 0
    if p1 > 0:
        k1 = k1 * 2 % p1
    k2 = k2 * 2 % p2
for i in range(N):
    print(ans[i])

Solution (Python):
n = int(input())
x = input()
temp = x.count("1")
mod1 = [1]
for i in range(n-1):
    mod1.append(mod1[-1] * 2 % (temp + 1))
mod1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += mod1[i]
        num1 %= (temp + 1)
if temp == 1 or temp == 2:
    mod2 = [0] * n
else:
    mod2 = [1]
    for i in range(n-1):
        mod2.append(mod2[-1] * 2 % (temp - 1))
    mod2.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += mod2[i]
            num2 %= (temp - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if temp == 1:
            print(0)
            continue
        elif temp == 2:
            print(1)
            continue
        else:
            num = num2 - mod2[i]
            num %= (temp - 1)
    else:
        num = num1 + mod1[i]
        num %= (temp + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]





N = ii()
S = input()

flag_m = [0]*(N)

flag_p = [0]*(N)
keta_list_m = [0]*(N)

keta_list_p = [0]*(N)

mod = S.count('1')

if mod == 1:
    flag_p[-1] = int(S[-1]) % (mod+1)
    keta_list_p[-1] = 1 % (mod+1)
    keta_p = 1
    for i in reversed(range(N-1)):
        keta_p *= 2
        keta_p %= (mod+1)
        keta_list_p[i] = keta_p
        if S[i] == '1':
            flag_p[i] = keta_p
    sum_f_p = sum(flag_p)

    for i in range(N):
        if S[i] == '1':
            print(0)
            continue
        else:
            num = (sum_f_p + keta_list_p[i]) % (mod+1)
    
        ans = 1
        if num == 0:
            print(ans)
            continue

        while True:
            cnt = 0
            tmp = 0
            while (1 << tmp) <= num:
                if num & 1 << tmp:
                    cnt += 1
                tmp += 1
            num %= cnt
            ans += 1
            if num == 0:
                print(ans)
                break
    exit()

flag_p[-1] = int(S[-1]) % (mod+1)
flag_m[-1] = int(S[-1]) % (mod-1)
keta_list_p[-1] = 1 % (mod+1)
keta_list_m[-1] = 1 % (mod-1)
keta_m = 1
keta_p = 1
for i in reversed(range(N-1)):
    keta_m *= 2
    keta_m %= (mod-1)
    keta_p *= 2
    keta_p %= (mod+1)
    keta_list_m[i] = keta_m
    keta_list_p[i] = keta_p
    if S[i] == '1':
        flag_p[i] = keta_p
        flag_m[i] = keta_m

sum_f_m = sum(flag_m)
sum_f_p = sum(flag_p)


for i in range(N):
    if S[i] == '1':
        num = (sum_f_m - keta_list_m[i]) % (mod-1)
    else:
        num = (sum_f_p + keta_list_p[i]) % (mod+1)
    

    ans = 1
    if num == 0:
        print(ans)
        continue

    while True:
        cnt = 0
        tmp = 0
        while (1 << tmp) <= num:
            if num & 1 << tmp:
                cnt += 1
            tmp += 1
        num %= cnt
        ans += 1
        if num == 0:
            print(ans)
            break

Solution (Python):
n = int(input())
s = input()
st = 0
for i in range(n):
    st += int(s[i])

if st == 1:
    if s[-1] == '1':
        for _ in range(n-1):
            print(2)
        print(0)
    else:
        for i in range(n):
            if s[i] == '1':
                print(0)
            elif i == n-1:
                print(2)
            else:
                print(1)
    exit()
m1 = [1]
p1 = [1]
for i in range(n-1):
    m1.append(m1[-1]*2%(st-1))
    p1.append(p1[-1]*2%(st+1))
if st-1 == 1:
    m1[0] = 0
if st+1 == 1:
    p1[0] = 0
m1.reverse()
p1.reverse()


ansm = 0
ansp = 0
for i in range(n):
    ansm += m1[i] * int(s[i])
    ansp += p1[i] * int(s[i])


time = [0 for _ in range(20)]
def nex(time):
    for i in range(20):
        if time[i] == 0:
            time[i] += 1
            return time
        else:
            time[i] = 0
ans = [0 for _ in range(200001)]
time2 = 1
time[0] = 1
while time2 <= 200000:
    
    ans[time2] = ans[time2 % sum(time)] + 1
    time = nex(time)
    time2 += 1


for i in range(n):
    if s[i] == '1':
        use = (ansm-m1[i]) % (st-1)
    else:
        use = (ansp+p1[i]) % (st+1)
    print(1+ans[use])

Solution (Python):
N = int(input())
X = int(input(), 2)

M = 2 * (10 ** 5) + 10
ret = [0] * (M + 1)
for i in range(M + 1) :
  x = i
  c = 0
  while x != 0 :
    x = x % bin(x).count('1')
    c += 1
  ret[i] = c
  
p = bin(X).count('1')
a = X % (p + 1)
if p > 1 :
  b = X % (p - 1)

for i in range(N - 1, -1, -1) :
  if (1 << i) & X :
    if p == 1 :
      print(0)
    else :
      print(ret[(b - pow(2, i, p - 1)) % (p - 1)] + 1)
  else :
    print(ret[(a + pow(2, i, p + 1)) % (p + 1)] + 1)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

m = 2*10**5+10
ans = [0] * m
for i in range(1,m):
    nnow = i
    res = 0
    stnow = bin(nnow).count('1')
    while nnow:
        
        nnow %= stnow
        stnow = bin(nnow).count('1')
        res += 1
    ans[i] = res


n = inp()
s = list(input())
tmp = s.count('1')
stm = tmp-1
stp = tmp+1
numm = 0
nump = 0
for i,x in enumerate(s):
    if x == '1': 
        nump += pow(2,n-i-1,stp)
        nump %= stp
        if stm > 0:
            numm += pow(2,n-i-1,stm)
            numm %= stm

for i in range(n):
    if s[i] == '0':
        nnow = (nump+pow(2,n-i-1,stp))%stp
    else:
        if stm <= 0:
            print(0)
            continue
        nnow = (numm-pow(2,n-i-1,stm))%stm
    
    print(ans[nnow]+1)

Solution (Python):
def solve(N, strX):
    def getNum1s(numD):
        num1s = [0] * (1<<numD)
        for S in range(1, 1<<numD):
            num1s[S] = num1s[S ^ (S & -S)] + 1
        return num1s
    num1s = getNum1s(20)

    fs = [0] * (N+1)
    for x in range(1, N+1):
        fs[x] = fs[x%num1s[x]] + 1

    M = strX.count('1')
    M1, M9 = M+1, M-1

    XmodM1 = 0
    for X in strX:
        XmodM1 *= 2
        XmodM1 += int(X)
        XmodM1 %= M1
    XmodM9 = 0
    for X in strX:
        XmodM9 *= 2
        XmodM9 += int(X)
        XmodM9 %= M9

    modM1s = []
    modM1 = 1
    for d in range(N+2):
        modM1s.append(modM1)
        modM1 *= 2
        modM1 %= M1

    modM9s = []
    modM9 = 1
    for d in range(N+2):
        modM9s.append(modM9)
        modM9 *= 2
        modM9 %= M9

    anss = []
    for X, modM1, modM9 in zip(strX[::-1], modM1s, modM9s):
        if X == '0':
            Y2 = (XmodM1 + modM1) % M1
        else:
            Y2 = (XmodM9 - modM9) % M9
        ans = fs[Y2] + 1
        anss.append(ans)

    return anss[::-1]


def solve2(N, strX):
    def getNum1s(numD):
        num1s = [0] * (1<<numD)
        for S in range(1, 1<<numD):
            num1s[S] = num1s[S ^ (S & -S)] + 1
        return num1s
    num1s = getNum1s(20)

    fs = [0] * (N+1)
    for x in range(1, N+1):
        fs[x] = fs[x%num1s[x]] + 1

    M = strX.count('1')
    M1, M9 = M+1, M-1

    XmodM1 = 0
    for X in strX:
        XmodM1 *= 2
        XmodM1 += int(X)
        XmodM1 %= M1

    modM1s = []
    modM1 = 1
    for d in range(N+2):
        modM1s.append(modM1)
        modM1 *= 2
        modM1 %= M1

    anss = []
    for X, modM1 in zip(strX[::-1], modM1s):
        if X == '0':
            Y2 = (XmodM1 + modM1) % M1
            ans = fs[Y2] + 1
        else:
            ans = 0
        anss.append(ans)

    return anss[::-1]


N = int(input())
strX = input().rstrip()

num1 = strX.count('1')

if num1 == 0:
    anss = [1] * N
elif num1 == 1:
    anss = solve2(N, strX)
else:
    anss = solve(N, strX)

print('\n'.join(map(str, anss)))

Solution (Python):
N=int(input())
X=input()

def popcount(x):
    return str(bin(x)).count("1")

cnt=[0]*N
for i in range(1,N):
    p = popcount(i)
    cnt[i]=cnt[i%p]+1


P=X.count("1")


MODSPP=[0]*N
MODSPM=[0]*N

PP=P+1
if P-1<=0:
    PM=1
else:
    PM=P-1

MODSPP[0]=1%PP
MODSPM[0]=1%PM

for i in range(1,N):
    MODSPP[i]=(MODSPP[i-1]*2)%PP
    MODSPM[i]=(MODSPM[i-1]*2)%PM



MODSX_PP=0
MODSX_PM=0
for i in range(N):
    if X[i]=="1":
        MODSX_PP+=MODSPP[N-i-1]
        MODSX_PM+=MODSPM[N-i-1]
    MODSX_PP%=PP
    MODSX_PM%=PM


for i in range(N):
    if X[i]=="0":
        ret=MODSX_PP+MODSPP[N-i-1]
        ret%=PP
        print(cnt[ret]+1)
    else:
        if P-1<=0:
            print(0)
        else:
            ret=(MODSX_PM-MODSPM[N-i-1]+PM)%PM
            print(cnt[ret]+1)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

def foo(y):
    ans = 0
    while y>0:
        z = y
        sm = 0
        for i in range(20):
            if (1<<i)&z != 0:
                sm += 1
                z -= 1<<i
                if z==0:
                    break
        y = y%sm
        ans += 1
    
    return ans

n = inn()
x = ins()
m = list(x).count('1')
xn = int(x,2)
xremm = xn%(m-1) if m>1 else 0
xremp = xn%(m+1)
iremm = [0]*n
iremp = [0]*n
if m>1:
    iremm[0] = 1
iremp[0] = 1
for i in range(1,n):
    iremp[i] = (2*iremp[i-1])%(m+1)
    if m>1:
        iremm[i] = (2*iremm[i-1])%(m-1)





for i in range(n):
    if x[i]=='1':
        if m==1:
            print(0)
        else:
            y = (xremm-iremm[n-1-i])%(m-1)
            print(foo(y)+1)
    else:
        y = (xremp+iremp[n-1-i])%(m+1)
        
        print(foo(y)+1)

Solution (Python):
N=int(input())
X=input()
def fx(n,c):
    if c==0:
        return 0
    b=n%c
    if b==0:
        return 1
    if b==1 or b==2:
        return 2
    t=bin(b).count("1")
    return fx(b,t)+1
c=X.count("1")
n=int(X,2)
lp=[1]*N
lm=[1]*N
for i in range(N-2,-1,-1):
    lp[i]=2*lp[i+1]%(c+1)
    if c==1:
        lm[i]=1
    else:
        lm[i]=2*lm[i+1]%(c-1)
np=n%(c+1)
if c>1:
    nm=n%(c-1)
else:
    nm=1
for i in range(N):
    if X[i]=="0":
        print(fx(np+lp[i],c+1))
    else:
        print(fx(nm-lm[i],c-1))

Solution (Python):





import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, X):
    o1 = ord("1")

    def f(n):
        p = bin(n).count("1")
        return n % p

    table = [0] * 20
    for i in range(1, 20):
        x = f(i)
        if x == 0:
            table[i] = 1
        else:
            table[i] = table[x] + 1

    numOne = X.count(o1)
    ret = [0] * N

    
    v = 0
    mod = numOne + 1
    p2mod_p1 = [0] * N
    p = 1
    for j in range(N):
        v *= 2
        v %= mod
        if (X[j] == o1):
            v += 1
        p2mod_p1[j] = p
        p *= 2
        p %= mod

    xmod_p1 = v % mod  
    xmod_m1 = 0  
    if numOne > 1:
        p = 1
        p2mod_m1 = [0] * N
        v = 0
        mod = numOne - 1
        for j in range(N):
            v *= 2
            v %= mod
            if (X[j] == o1):
                v += 1
            xmod_m1 = v % mod
            p2mod_m1[j] = p
            p *= 2
            p %= mod

    
    

    for i in range(N):
        if X[i] == o1:
            mod = numOne - 1
            if mod == 0:
                
                ret[i] = 0
                continue
            v2 = (xmod_m1 - p2mod_m1[-1-i]) % mod
        else:
            mod = numOne + 1
            v2 = (xmod_p1 + p2mod_p1[-1-i]) % mod
        
        
        
        
        
        
        
        
        
        v = v2

        
        if v == 0:
            ret[i] = 1
            continue
        if v < 20:
            ret[i] = table[v] + 1
            continue

        v = f(v)
        ret[i] = table[v] + 2

    
    
    return ret


def main():
    
    N = int(input())
    X = input().strip()
    print(*solve(N, X), sep="\n")



T1 = """
3
011
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    2
    1
    1
    """


T2 = """
23
00110111001011011001110
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    2
    1
    2
    2
    1
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    2
    1
    3
    """


T3 = """
100
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
"""











def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
n = int(input())
x = input()
def cal(num):
    A = 1
    while num>0:
        X = bin(num)
        X = str(X)
        Y = X.count("1")
        num = num%Y
        A += 1
    return(A)
y = x.count("1")
if (y==0):
    ans = [1]*n
    print(*ans, sep="\n")
    exit()
elif (y==1):
    w1 = []
    wa = 1
    for i in range(n):
        wa %= y+1
        w1.append(wa)
        wa *= 2
    w1.reverse()
    a1 = 0
    for i in range(n):
        if (x[i]=="1"):
            a1 += w1[i]
    a1 %= y+1
    ans = []
    for i in range(n):
        if (x[i]=="0"):
            tnp = a1
            tnp += w1[i]
            tnp %= y+1
            ans.append(cal(tnp))
        else:
            ans.append(0)
    print(*ans, sep="\n")
    exit()
        
w1 = []
w2 = []
wa = 1
for i in range(n):
    wa %= y+1
    w1.append(wa)
    wa *= 2
wa = 1
for i in range(n):
    wa %= y-1
    w2.append(wa)
    wa *= 2

w1.reverse()
w2.reverse()
a1 = 0
a2 = 0
for i in range(n):
    if (x[i]=="1"):
        a1 += w1[i]
        a2 += w2[i]
a1 %= y+1
a2 %= y-1

ans = []
for i in range(n):
    if (x[i]=="0"):
        tnp = a1
        tnp += w1[i]
        tnp %= y+1
        ans.append(cal(tnp))
    else:
        tnp = a2
        tnp -= w2[i]
        tnp %= y-1
        ans.append(cal(tnp))
    
print(*ans, sep="\n")

Solution (Python):
n = int(input())
x = input()
mod_num1 = [0 for i in range(n+1)]
mod_num2 = [0 for i in range(n+1)]
mod_num3 = [0 for i in range(n+1)]
num2 = x.count('1')
if num2 == 0:
    for i in range(n):
        print(1)
    exit()
elif num2 == 1:
    index = x.index('1')
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            if index == n-1 or i == n-1:
                print(2)
            else:
                print(1)
    exit()
num1 = num2 - 1
num3 = num2 + 1
for i in range(n):
    if x[i] == '1':
        mod_num1[i] = pow(2, n-i-1 ,num1)
        mod_num2[i] = pow(2, n-i-1, num2)
        mod_num3[i] = pow(2, n-i-1, num3)
def popcount(num):
    res = 0
    while num != 0:
        res += 1
        num = num % "{:b}".format(num).count('1')
    return res
s_1 = sum(mod_num1)
s_2 = sum(mod_num2)
s_3 = sum(mod_num3)
for i in range(n):
    if x[i] == '1':
        print(popcount((s_1 - pow(2, n-i-1, num1)) % num1) + 1)
    else:
        print(popcount((s_3 + pow(2, n-i-1, num3)) % num3) + 1)

Solution (Python):
def popcount(n):
    count = 0
    while n !=0:
        k = bin(n)[2:len(bin(n))].count("1")
        n = n%k
        count+=1
    return count


N = int(input())

X = list(map(int,list(input())))

c = X.count(1)

amari_c = 0
amari_c_dic = 0
amari_c_inc = 0

for i in range(0,N,1):
    if c > 0:
        amari_c = (amari_c + X[N-i-1]*pow(2,i,c))%c
    if c-1 > 0:
        amari_c_dic = (amari_c_dic + X[N-i-1]*pow(2,i,c-1))%(c-1)
    amari_c_inc = (amari_c_inc + X[N-i-1]*pow(2,i,c+1))%(c+1)

for i in range(0,N,1):
    if X[i]==0:
            tmp = (amari_c_inc + pow(2,N-i-1,c+1))%(c+1)
            print(1+popcount(tmp))

    elif X[i]==1:
        if c-1 >0:
            tmp = (amari_c_dic - pow(2,N-i-1,c-1))%(c-1)
            print(1+popcount(tmp))
        else:
            print(0)

Solution (Python):
def func(N):
    return N%bin(N).count("1")

N = int(input())
X = input()

popcount = X.count("1")
X_num = int(X,2)

O = X_num%(popcount+1)
if popcount==1:
    I = 0
else:
    I = X_num%(popcount-1)

bO = 1
bI = 1

ans= []
for i in range(N):
    if X[-1-i]=="0":
        hoge = (O + bO)%(popcount+1)
    else:
        if popcount==1:
            ans.append(0)
            continue
        hoge = (I - bI)%(popcount-1)
    count = 1
    while hoge:
        hoge = func(hoge)
        count += 1
    ans.append(count)
    bO = (bO*2)%(popcount+1)
    if popcount != 1:
        bI = (bI*2)%(popcount-1)

for i in range(N):
    print(ans[-1-i])

Solution (Python):
N = int(input())
X = list(map(int, input()))[::-1]
p = sum(X)

if p==0:
    for _ in range(N):
        print(1)
    exit()

if p==1:
    if X[0]==0:
        ans = [2]
        for n in range(1, N):
            ans.append(1 if X[n]==0 else 0)
    else:
        ans = [0] + [2]*(N-1)

    for a in ans[::-1]:
        print(a)
        
    exit()
    

pp = p+1
rp = []
k = 1
for n in range(N):
    rp.append(k%pp)
    k = k*2%pp

sp = 0
for r,x in zip(rp, X):
    if x==1: sp = (sp+r)%pp
    
pn = p-1
rn = []
k = 1
for n in range(N):
    rn.append(k%pn)
    k = k*2%pn

sn = 0
for r,x in zip(rn, X):
    if x==1: sn = (sn+r)%pn

def popcount(x):
    p = 0
    while x:
        p += x&1
        x>>=1
    return p

def op(x):
    p = popcount(x)
    return x%p

def f(x):
    n = 0
    while x:
        n+=1
        x = op(x)
    return n
    
ans = []
for n,x in enumerate(X):
    if x==0:
        ans.append(1+f((sp+rp[n])%pp))
    else:
        ans.append(1+f((sn-rn[n])%pn))

for a in ans[::-1]:
    print(a)

Solution (Python):
N = int(input())
X = list(input())
X = [int(x) for x in X]
X.reverse()

def popcnt0(n):
    c = 0
    for i in range(64):
        c += (n >> i) & 1
    return c
  

D = [0 for _ in range(N+1)]
D[1] = 1
for i in range(2, N+1):
  D[i] = D[i % popcnt0(i)] + 1
  

ct_1 = 0
for x in X:
  if x == 1:
    ct_1 += 1


if ct_1 > 1:
  B = [0 for _ in range(N)]
  j = 1
  for i in range(N):
    B[i] = j
    j *= 2
    j %= ct_1 - 1 



C = [0 for _ in range(N)]
j = 1
for i in range(N):
  C[i] = j
  j *= 2
  j %= ct_1 + 1 


s = 0
t = 0
for i in range(N):
  if ct_1 > 1:
    s += X[i] * B[i]
    s %= ct_1-1
  t += X[i] * C[i] 
  t %= ct_1+1

X.reverse()


i = N-1

for x in X:
  if x == 1:
    if ct_1 > 1:
      k = (s - B[i]) % (ct_1-1)
    else:
      print(0)
  else:
    k = (t + C[i]) % (ct_1+1)        
  i -= 1
  if ct_1 > 1 or x == 0:
    print(D[k]+1)