program pr4
  implicit none
  integer :: i, j, k, n, c
  character(len=200000) :: xchar
  integer,allocatable :: x(:), x1(:)
  
  read(*,*) n
  allocate(x(n), x1(n))
  read(*,*) xchar
  do i = 1, n
     read(xchar(i:i),*) x(i)
  end do

  x1 = x

  do j = 1, n
     if ( x1(j) == 1 ) then
        x1(j) = 0
     else
        x1(j) = 1
     end if
     
     if ( sum(x1) == 0 ) then
        write(*,'(i0)') 0
        cycle
     end if
     
     call bin2dec(x1,k)
     k = mod(k,sum(x1))

     c = 1
     do
        if ( k == 0 ) then
           exit
        end if
        call dec2bin(k,x1)
        k = mod(k,sum(x1))
        c = c + 1
     end do
        
     write(*,'(i0)') c
        
     x1(:) = x(:)
  end do

  deallocate(x,x1)
  stop

contains

  subroutine bin2dec(x,k)
    implicit none
    integer,intent(in) :: x(:)
    integer :: n, i, j, k
    n = size(x)
    k = 0
    
    do i = 1, n
       k = k + x(i)*(2**(n-i))
    end do
    return
  end subroutine bin2dec
  
  subroutine dec2bin(a,b)    !2進数を配列の形で出力
    implicit none
    integer, intent(in) :: a
    integer :: b(:)
    integer :: memory

    memory = a
    do i = size(b) - 1, 0, -1
       b(size(b)-i) = memory / (2**i)
       memory = memory - (2**i) * b(size(b)-i)
    end do
    
  end subroutine dec2bin
end program pr4
