N,x = gets.to_i,gets
c,x = x.scan(?1).count, x.to_i(2)
R = [1,-1].map { m = c+_1; x%m if m>1 }
D = R.map { _1 ? 1 : 0 }
M = {0=>1}
X = (0...N).map {|n|
  b = x[n]
  d,r,m = D[b],R[b],c+1-b-b
  D[0] -= c+1  if c < D[0]<<=1
  D[1] -= c-1  if c-1 <= D[1]<<=1
  if m < 2
    m - 2
  elsif b > 0
    (0 > r-=d) ? r+m : r
  else
    (c < r+=d) ? r-m : r
  end
}.reverse!
I = [*0...N].sort_by! {X[_1]}
S = []
I.each {|i|
  next  if 1 > x=X[i]
  until c=M[x]
    S << x
    b,c = x+x,0
    c+=b[0] while 0 < (b>>=1)
    x %= c
  end
  M[x] = c+=1  while x=S.pop
}
X.each {|x| p x<0 ? x+2 : M[x]}