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):
n = int(input())
x = input()
t = int(x, 2)
c = x.count('1')
a = t % -~c
b = 0 if c < 2 else t % ~-c
for i in range(n):
    if int(x[i]):
        if c < 2:
            print(0)
            continue
        else:
            t = (b-pow(2, n-i-1, c-1)) % ~-c
    else:
        t = (a+pow(2, n-i-1, c+1)) % -~c
    z = 1
    while t:
        d = bin(t).count('1')
        t %= d
        z += 1
    print(z)

Solution (Python):
def fun(n):
    ops = 0
    while n:
        pc = format(n, 'b').count('1')
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = input()

sm = int(xs, 2)
pc = xs.count('1')

mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i, x in enumerate(xs, 1):
    df = 1 if x == '0' else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i, pci)

    if x == '0':
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Solution (Python):
from collections import Counter

N = int(input())
X = input()
cnt = X.count('1')
memo = [0]*(N+1)
memo2 = [[0]*(N+1) for _ in range(2)]
memo2[0][1] = memo2[1][1] = 1

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

for i in range(1,N+1):
  if i == 1:
    if cnt > 1:
      memo2[0][i] = 1 % (cnt-1)
    memo2[1][i] = 1 % (cnt+1)
  else:
    if cnt > 1:
      memo2[0][i] = memo2[0][i-1]*2 % (cnt-1)
    memo2[1][i] = memo2[1][i-1]*2 % (cnt+1)
  t = 0
  a = i
  while a > 0:
    b = bin(a).count('1')
    a %= b
    t += 1
  memo[i] = t
  
X1 = 0
X_1 = 0
for i in range(1,N+1):
  if X[N-i] == '1':
    X1 += memo2[1][i]
    X_1 += memo2[0][i]
    X1 %= cnt+1
    if cnt > 1:
      X_1 %= cnt-1
    
for i in range(N,0,-1):
  Y = 0
  if X[N-i] == '1':
    if cnt == 1:
      print(0)
      continue
    Y = X_1 - memo2[0][i]
    if Y < 0:
      Y += cnt - 1
    print(memo[Y]+1)
  else:
    Y = X1 + memo2[1][i]
    Y %= cnt + 1
    print(memo[Y]+1)

Solution (Python):

from collections import defaultdict, deque


def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    xor_set = 1 % (x_count+1)
    if 1 < x_count:
        x_mod_reset = x_dec % (x_count-1)
        xor_reset = 1 % (x_count-1)

    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(str(0))
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        if 1 < x_count:
            xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
def f(n,cnt):
    if n==0:
        return cnt
    popcnt = bin(n).count('1')
    return f(n%popcnt,cnt+1)

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

m = int(x,2)
m_cnt = x.count('1')

mp = m%(m_cnt+1)
mm = m%(m_cnt-1) if m_cnt > 1 else 0

for i,s in enumerate(x):
    i = n-1-i
    num = None

    if s == '0':
        mod = m_cnt+1
        num = (mp+pow(2,i,mod))%mod
    elif m_cnt > 1:
        mod = m_cnt-1
        num = (mm-pow(2,i,mod))%mod
    else:
        print(0)
        continue

    print(1+f(num,0))

Solution (Python):
from numba import njit

@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        pc = popcount(n)
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)


mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i in range(n):
    df = 1 if xs[i] == 0 else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i - 1, pci)

    if xs[i] == 0:
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))

Solution (Python):
import numpy as np

N = int(input())
X = input()[::-1]
mod = X.count('1')
listX = np.array(list(X), int)

def simulate(num):
    counter = 0
    while num > 0:
        num %= bin(num).count('1')
        counter += 1
    return counter

if mod == 1:
    coefP = np.array([pow(2,i,mod+1) for i in range(N)])
    posi = np.dot(coefP, listX) % (mod+1)

    ans = []
    for i,x in enumerate(X):
        if x == '0':
            num = (posi + coefP[i]) % (mod+1)
            ans.append(simulate(num) + 1)
        else:
            ans.append(0)
    print(*ans[::-1], sep='\n')

else:
    coefP = np.array([pow(2,i,mod+1) for i in range(N)])
    coefN = np.array([pow(2,i,mod-1) for i in range(N)])
    posi = np.dot(coefP, listX) % (mod+1)
    nega = np.dot(coefN, listX) % (mod-1)

    ans = []
    for i,x in enumerate(X):
        if x == '0':
            num = (posi + coefP[i]) % (mod+1)
            ans.append(simulate(num) + 1)
        else:
            num = (nega - coefN[i]) % (mod-1)
            ans.append(simulate(num) + 1)
    print(*ans[::-1], sep='\n')

Solution (Python):
n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    if c<2: print(0); continue
    else: t=(b-pow(2,n-i-1,c-1))%~-c
  else: t=(a+pow(2,n-i-1,c+1))%-~c
  z=1
  while t:
    d=bin(t).count('1')
    t%=d
    z+=1
  print(z)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  

N = I()

A = [0]  
for i in range(1,N):
    a = 0  
    for j in range(18):
        a += (i >> j) & 1
    A.append(1 + A[i % a])

X = LS2()

b = 0  
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()

    
    

    r1,r2 = 0,0  
    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()

    

    r2 = 0  
    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')

Solution (Python):
def bitcount(N):  
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        if cnt == 1:
            print(0)
            continue
        ctmp = cnt - 1
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Solution (Python):
def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            
        d_li[i] = ans
    
    
    
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    
    
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    
    t_v_p = val % (mod+1)
    if mod == 1:
        t_v_m = 0
    else:
        t_v_m = val % (mod-1)
        
    for i in range(n):
        ans = 0
        
        
        if int(x[i]) == 1:
            if mod == 1:
                t_v = 0
            else:
                t_v = t_v_m
                t_v -= pow(2,(n-1-i),mod-1)
                
                t_v %= (mod-1)
                ans += 1
                
        else:
            t_v = t_v_p
            t_v += pow(2,(n-1-i),mod+1)
            
            
            t_v %= (mod+1)
            ans += 1
            
        rui //= 2
        
        
        """
        if t_v != 0:
            if int(x[i]) == 1:
                if mod == 1:
                    t_v = 0
                else:
                    t_v %= mod-1
            else:
                t_v %= mod + 1
            
            ans += 1
        """
        ans += d_li[t_v]
        
        
        print(ans)
        
        
if __name__ == '__main__':
    main()
"""

for i in range(n):
    print(ans_li[n-1-i])
"""

Solution (Python):
def main():
    n = int(input())
    x = input()
    
    val = 0
    rui = 1
    mod = 0
    
    nagasa = 2*10**5+1
    
    d_li = [0]*(nagasa)
    
    for i in range(1,nagasa):
        t_v = i
        t_m = bin(t_v).count("1")
        ans = 0
        while t_v != 0:
            if d_li[t_v] != 0:
                ans += d_li[t_v]
                break
            ans += 1
            t_v %= t_m
            
        d_li[i] = ans
    
    
    
    """
    for i in range(n):
        val += int(x[n-1-i])*rui
        rui *= 2
    """
    val = int(x, 2)
    
    
    
    mod = bin(val).count("1")
    
    rui = pow(2,(n-1))
    
    t_v_p = val % (mod+1)
    if mod == 1:
        t_v_m = 0
    else:
        t_v_m = val % (mod-1)
        
    for i in range(n):
        ans = 0
        
        
        if int(x[i]) == 1:
            if mod == 1:
                t_v = 0
            else:
                t_v = t_v_m
                t_v -= pow(2,(n-1-i),mod-1)
                
                t_v %= (mod-1)
                ans += 1
                
        else:
            t_v = t_v_p
            t_v += pow(2,(n-1-i),mod+1)
            
            
            t_v %= (mod+1)
            ans += 1
            
        rui //= 2
        
        
        """
        if t_v != 0:
            if int(x[i]) == 1:
                if mod == 1:
                    t_v = 0
                else:
                    t_v %= mod-1
            else:
                t_v %= mod + 1
            
            ans += 1
        """
        ans += d_li[t_v]
        
        
        print(ans)
        
        
if __name__ == '__main__':
    main()
"""

for i in range(n):
    print(ans_li[n-1-i])
"""

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
from sys import flags
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
x=list(input())
cnt=Counter(x)
x2=int("".join(x),2)
one=cnt["1"]




lst=[0]*(2*10**5+10)

flaglst=[0,0]
if one-1!=0:
    flaglst[0]=x2%(one-1)
flaglst[1]=x2%(one+1)


for i in range(2*10**5):
    now=i+1
    ans=0
    while now:
        cnt2=0
        m=0
        while now>=pow(2,m):
            if now&1<<m:
                cnt2+=1
            m+=1
        now%=cnt2
        ans+=1
    lst[i+1]=ans


for i in range(n):
    tmp=0
    if x[i]=="1":
        tmp=flaglst[0]
        if one-1!=0:
            tmp-=pow(2,n-1-i,one-1)
            tmp%=one-1
        else:
            print(0)
            continue
    else:
        tmp=x2%(one+1)
        tmp+=pow(2,n-1-i,one+1)
        tmp%=one+1
    

    print(lst[tmp]+1)

Solution (Python):
def bitcount(N):  
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

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

cnt = X.count("1")
res0 = 0
res1 = 0
for i in range(N):
    if X[i] == "1":
        res0 = (res0 + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)

        if cnt - 1 > 0:
            res1 = (res1 + pow(2, N - i - 1, cnt - 1)) % (cnt - 1)

for i in range(N):
    ans = 0
    if X[i] == "0":
        div = cnt + 1
        tmp = (res0 + pow(2, N - i - 1, div)) % div
        ans += 1
    else:
        if cnt - 1 > 0:
            div = cnt - 1
            tmp = (res1 + div - pow(2, N - i - 1, div)) % div
            ans += 1
        else:
            tmp = 0

    while tmp > 0:
        ans += 1
        div = bin(tmp).count("1")
        tmp %= div
        
    print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    N=int(input())
    X=input().strip("\n")
    cnt=[0]*N
    for i in range(1,N):
        n=i
        while(n>0):
            pc=0
            for j in range(19):
                if (n>>j)&1==1:
                    pc+=1
            n%=pc
            cnt[i]+=1
    pc=X.count("1")
    if pc==0:
        for i in range(N):
            print(1)
        exit()

    rp=[0]*N
    rn=[0]*N
    for i in range(N):
        rp[i]=pow(2,i,pc+1)
        if pc!=1:
            rn[i]=pow(2,i,pc-1)
    rp=rp[::-1]
    rn=rn[::-1]
            
    Xrp=0
    Xrn=0
    for i in range(N):
        if X[i]=="1":
            Xrp=(Xrp+rp[i])%(pc+1)
            if pc!=1:
                Xrn=(Xrn+rn[i])%(pc-1)
            
    for i in range(N):
        if X[i]=="1":
            if pc==1:
                print(0)
                continue
            r=Xrn-rn[i]
            print(cnt[r%(pc-1)]+1)
        else:
            r=Xrp+rp[i]
            print(cnt[r%(pc+1)]+1)
    
    
    
if __name__=="__main__":
    main()

Solution (Python):
def bitcount(N):  
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Solution (Python):
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    cache={"0":0}
    def get_pc(s):
        pc = sum([c == '1' for c in s])
        return pc

    def modPC(s,pc=None):
        if pc==None:
            pc =get_pc(s)
        return int(s,2)%pc

    def f(s,cur=0):
        if s in cache:
            return cache[s]
        next_s = bin(modPC(s))[2:]
        ret = f(next_s,cur+1)+1
        cache[s]=ret
        return ret
    N=iRaw()
    Xs=sRaw()
    XPC = get_pc(Xs)
    XmodPC=None
    if XPC!=0:
        XmodPC = modPC(Xs,XPC)
    XmodPCP = modPC(Xs,XPC+1)
    XmodPCN = None
    if XPC>1:
        XmodPCN= modPC(Xs,XPC-1)

    for n in range(N):
        if Xs[n]=='1':
            if XPC==1:
                print(0)
            else:
                nxt=(XmodPCN-pow(2,N-n-1,XPC-1))%(XPC-1)
                nxt = bin(nxt)[2:]
                print(f(nxt)+1)
        else:
            nxt = (XmodPCP+pow(2, N-n-1, XPC+1)) % (XPC+1)
            nxt = bin(nxt)[2:]
            print(f(nxt)+1)

main()

Solution (Python):
import sys 

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

pc = X.count("1")



mod_sum = {pc-1:0, pc+1:0}

for i in range(N):
    for this_pc in (pc-1, pc+1):
        if this_pc == 0:
            mod_sum[this_pc] = 0
            break
        if X[i] == "1":
            mod_sum[this_pc] += pow(2, N-i-1, this_pc)
            mod_sum[this_pc] %= this_pc
            


for i in range(N):
    tmp_pc = pc
    if X[i] == "0":
        tmp_pc += 1
    else:
        tmp_pc -= 1
    if tmp_pc == 0:
        print(0)
        continue

    if X[i] == "0":
        tmp_mod_sum = mod_sum[tmp_pc] + pow(2, N-i-1, tmp_pc)
        tmp_mod_sum %= tmp_pc
    else:
        tmp_mod_sum = mod_sum[tmp_pc] - pow(2, N-i-1, tmp_pc)
        tmp_mod_sum %= tmp_pc

    count = 1
    tmp_sum = tmp_mod_sum
    
    
    while tmp_sum > 0:
        tmp_x = str(bin(tmp_sum))
        tmp_pc = tmp_x.count("1")
        count += 1
        if tmp_pc == 0:
            break
        tmp_sum = tmp_sum % tmp_pc
        
    print(count)

Solution (Python):
def bitcount(N):  
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


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

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Solution (Python):
N = int(input())
X = ["0"] + list(input())


def popcount(x):
    c = 0
    while x > 0:
        if x % 2 == 1:
            c += 1
        x //= 2
    return c


def count(x):
    c = 0
    while x > 0:
        p = popcount(x)
        x %= p
        c += 1
    return c


p0 = X.count("1")
Xp, Xm = 0, 0  
for i in range(1, N + 1):
    if X[i] == "1":
        Xp += pow(2, N - i, p0 + 1)
Xp %= p0 + 1
if p0 > 1:
    for i in range(1, N + 1):
        if X[i] == "1":
            Xm += pow(2, N - i, p0 - 1)
    Xm %= p0 - 1
else:
    Xm = 0

for i in range(1, N+1):
    if X[i] == "1":
        p1 = p0 - 1
        if p1 == 0:
            print(0)
        else:
            x = (Xm + p1 - pow(2, N-i, p1)) % p1
            print(count(x)+1)
    else:
        p1 = p0 + 1
        x = (Xp + pow(2, N-i, p1)) % p1
        print(count(x)+1)

Solution (Python):
from collections import defaultdict
def main():
    N = int(input())
    S = input()
    D = defaultdict(bool)
    cnt = 0
    all1 = 0
    all2 = 0
    for i in range(N):
        if S[i] == "1":
            D[i] = True
            cnt += 1
        else:
            D[i] == False

    for i in range(N):
        if S[i] == "1":
            all1 += pow(2, N-1-i, cnt+1)
            if cnt != 1:
                all2 += pow(2, N-1-i, cnt-1)

    for i in range(N):
        P = 0
        if S[i] == "1":
            if cnt == 1:
                print(0)
                continue
            else:
                P += all2-pow(2, N-1-i, cnt-1)
            ans = 1
            P = P % (cnt-1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
            continue
        else:
            P += all1+pow(2, N-1-i, cnt+1)
            ans = 1
            P = P % (cnt+1)
            while P:
                c = P
                mod = 0
                while c:
                    mod += c & 1
                    c = c >> 1
                P = P % mod
                ans += 1
            print(ans)
if __name__=="__main__":
    main()

Solution (Python):
def main():
    N = int(input())
    *X, = map(int, input())

    popcount = X.count(1)

    if popcount == 1:
        ans = []
        for i, d in enumerate(X):
            if d:  
                ans.append(0)  
                continue
            else:  
                if i == N - 1 or X[N - 1]:
                    ans.append(2)  
                else:
                    ans.append(1)  

        print(*ans, sep='\n')
        return

    def get_total(off: bool):
        """bit反転操作前のXを
        bit反転操作後のpopcountで割った剰余
        各桁のbit反転した整数は
        ここで求めたsに差分を加減すれば求まる
        """
        if off:  
            mod = popcount - 1
        else:  
            mod = popcount + 1

        s = 0
        for d in X:
            s = (s * 2 + d) % mod
        return s

    tot_off = get_total(off=True)
    tot_on = get_total(off=False)

    ans = []
    for i, d in enumerate(X):
        
        
        if d:  
            mod = popcount - 1
            tot = (tot_off - pow(2, N - 1 - i, mod)) % mod
        else:  
            mod = popcount + 1
            tot = (tot_on + pow(2, N - 1 - i, mod)) % mod

        cnt = 1
        while tot:  
            tot %= bin(tot)[2:].count('1')
            cnt += 1

        ans.append(cnt)

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


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
x = input()

num_of_1 = x.count("1")

x_num = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

a = x_num % (num_of_1 + 1)
b = x_num % (num_of_1 - 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((a + pow(2, n-i-1, num_of_1 + 1)) % (num_of_1 + 1)))
    else:
        print(1 + f((b - pow(2, n-i-1, num_of_1 - 1)) % (num_of_1 - 1)))

Solution (Python):
n = int(input())
x = input()

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((first_zero + pow(2, n-i-1, num_of_1 + 1)) % (num_of_1 + 1)))
    else:
        print(1 + f((first_one - pow(2, n-i-1, num_of_1 - 1)) % (num_of_1 - 1)))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()

def bitcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''
    
    x = x - ((x >> 1) & 0x5555555555555555)
    
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

def popcount(n):
    cnt = 0
    while n:
        n %= bitcount(n)
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        if not bn == 1:
            modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

print(*ans, sep="\n")

Solution (Python):
n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")
xc0 = x10 % (maxbit + 1)
xc1 = x10 % (maxbit - 1) if maxbit > 1 else 0

def f(ii):
  cnt = 0
  while ii > 0:
    ii %= bin(ii).count("1")
    cnt += 1
  return cnt

for i in range(lenx):
  if x[i] == "0":
    t = xc0 + pow(2, (lenx - 1 - i), maxbit + 1)
    ans = f(t % (maxbit + 1)) + 1
  else:
    if maxbit - 1 == 0:
      ans = 0
    else:
      t = xc1 - pow(2, (lenx - 1 - i), maxbit - 1)
      ans = f(t % (maxbit - 1)) + 1
  print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

pc = X.count("1")


if pc == 0:
    for i in range(N):
        print(1)
    exit()

sml = pc - 1
big = pc + 1

b = 0
mod_s = 0
mod_b = 0
for x in X[::-1]:
    if x == "1":
        if sml:
            mod_s += pow(2, b, sml)
            mod_s %= sml

        mod_b += pow(2, b, big)
        mod_b %= big

    b += 1




ELE = []

b = 0
for x in X[::-1]:
    if x == "0":
        t = (mod_b + pow(2, b, big)) % big
        ELE.append((t, 1))
    else:
        t = (mod_s - pow(2, b, sml)) % sml if sml else 0

        if sml:
            ELE.append((t, 1))
        else:
            ELE.append((0, 0))
    b += 1


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

    b = 0
    nx = x
    while nx > 0:
        b += nx & 1
        nx >>= 1

    ret = solve(x % b, c + 1)
    return ret


ANS = []
for x, pc in ELE:
    ANS.append(solve(x, pc))

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    X = input()
    bit_num = X.count("1")

    X_minus = [0] * N 
    X_plus = [0] * N 
    X_minus[0], X_plus[0] = 1, 1
    for i in range(1, N):
        if bit_num != 1: X_minus[i] = (X_minus[i - 1] * 2) % (bit_num - 1)
        X_plus[i] = (X_plus[i - 1] * 2) % (bit_num + 1)
    
    

    rem_minus = 0
    rem_plus = 0
    for i in range(N):
        if X[N-i-1] == '1':
            if bit_num != 1: rem_minus = (rem_minus + X_minus[i]) % (bit_num - 1)
            rem_plus = (rem_plus + X_plus[i]) % (bit_num + 1)
    

    for i in range(N):
        if X[i] == '0':
            bit = bit_num + 1
            n = (rem_plus + X_plus[-i-1]) % bit
        if X[i] == '1':
            bit = bit_num - 1
            if bit != 0: n = (rem_minus - X_minus[-i-1]) % bit
        if bit == 0 or bit == 1:
            print(bit)
            continue

        cnt = 1
        while n != 0:
            bit = bin(n).count("1")
            n %= bit
            cnt += 1
        print(cnt)




if __name__ == "__main__":
    main()