Scanf.scanf "%d %s" (fun n x ->
    let rec loop i acc =
        if i = n then acc else
            if x.[i] = '1' then loop (i + 1) (acc + 1)
                           else loop (i + 1) acc
    in

    let longdiv bits =
        let rec loop pos rest =
            if pos = n then rest else
                let rest = rest * 2 + (if x.[pos] = '1' then 1 else 0) in
                let rest = rest mod bits in
                loop (pos + 1) rest
        in
        loop 0 0
    in

    let bits = loop 0 0 in
    let imp = longdiv (bits + 1) in
    let imm = if bits > 2 then longdiv (bits - 1) else 1 in

    let popcount a =
        let rec loop rest acc =
            if rest = 0 then acc else loop (rest lsr 1) (acc + (rest land 1))
        in
        loop a 0
    in
    let powmod a b m =
        let rec loop r x acc =
            if x = 0 then acc else
                loop ((r * r) mod m) (x lsr 1) (if x land 1 = 1 then (r * acc) mod m else acc)
        in
        loop a b 1
    in
    let rec phase2 md c =
        if md = 0 then c else phase2 (md mod (popcount md)) (c + 1)
    in
    let calc i =
        if x.[i] = '1' && bits = 1 then 0 else
            let md = if x.[i] = '1' then ((imm - powmod 2 (n - i - 1) (bits - 1)) mod (bits - 1) + (bits - 1)) mod (bits - 1)
                                    else (imp + powmod 2 (n - i - 1) (bits + 1)) mod (bits + 1)
            in
            phase2 md 1
    in
    for i = 0 to n - 1 do
        Printf.printf "%d\n" @@ calc i
    done
)
