N=gets.to_i
S=gets
pc=S.count ?1
X=S.to_i(2)
xl=pc==1 ? 0 : X%~-pc
xr=X%-~pc
f=[0]
1.upto(N){f<<f[_1%('%b'%_1).count(?1)]+1}
N.times{nc=S[_1][?1] ? pc-1 : pc+1
p nc==0 ? 0 : f[nc==pc+1 ? (xr+2.pow(N+~_1,nc))%nc : (xl-2.pow(N+~_1,nc))%nc]+1}