local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end
local function array(dimension, default_val) assert(type(default_val) ~= 'table') local n=dimension local m={}if default_val~=nil then m[1]={__index=function()return default_val end}end for i=2,n do m[i]={__index=function(p, k)local c=setmetatable({},m[i-1])rawset(p,k,c)return c end}end return setmetatable({},m[n])end
local function tostringxx(o, depth) depth = depth or 0 if depth > 10 then return "<too deep!>" end if o == _G then return "<_G>" end local indent0 = (" "):rep((depth) * 2) local indent1 = (" "):rep((depth+1) * 2) local indent2= (" "):rep((depth+2) * 2) if type(o) == 'table' then local keys = {} local types = {} for k in pairs(o) do types[type(k)] = true table.insert(keys, k) end local types_count = 0 local lasttype for k in pairs(types) do types_count = types_count + 1 lasttype = k end if types_count == 1 and (lasttype == 'string' or lasttype == 'number') then table.sort(keys) end local inside = {} for i=1,#keys do local k = keys[i] local v = o[k] if type(k) == 'string' then k = string.format('%q', k) end table.insert(inside, indent1 .. '['..tostring(k)..'] = ' .. tostringxx(v, depth + 1)) end return '{\n' .. table.concat(inside, ',\n') .. '\n' .. indent0 .. '}' else if type(o) == 'string' then o = string.format('%q', o) end return tostring(o) end end
local function richtraceback() local x = 2 while true do local info = debug.getinfo(x) if not info then break end local fname = '<' .. info.short_src .. ":" .. info.linedefined .. ">" if info.name then fname = info.name end print(info.short_src .. ":" .. info.currentline .. ": in " .. ("%q"):format(fname)) print(" LOCALS:") local p = 1 while true do local name, val = debug.getlocal(x,p) if not name then break end print(" " .. name .. ": " .. tostringxx(val, 3)) p = p + 1 end print(" UPVALUES:") for p=1,info.nups do local name, val = debug.getupvalue(info.func,p) if not name then break end print(" " .. name .. ": " .. tostringxx(val, 3)) end x = x + 1 end end
local function myassert(b) if not b then richtraceback() error("assertion failed") end end 
-----------------------
----
local function popcount(n)
    local t = {}
    while n > 0 do
        table.insert(t, n % 2)
        n = n // 2
    end
    local p = 0
    for i=1,#t do
        p = p + t[i]
    end
    return p
end

local function f_naive(n)
    local c = 0
    while n ~= 0 do
        n = n % popcount(n)
        c = c + 1
    end
    return c
end

----
local N = read.nl()
local Xs = read.l():totable()
local pop0 = 0
for i=1,N do
    if Xs[i] == "1" then
        pop0 = pop0 + 1
    end
end
if pop0 == 0 then
    for i=1,N do
        print(1)
    end
    return
end
if pop0 == 1 then
    if Xs[N] == "1" then
        -- 00000....00001
        for i=1,N-1 do
            -- 00100...00001 (popcount=2) -> 1 (popcount=1) -> 0
            print(2)
        end
        -- 0 (popcount=0)
        print(0)
        return
    else
        -- 00000....00100....0000
        for i=1,N-1 do
            if Xs[i] == "1" then
                -- 0
                print(0)
            else
                -- 0000....00100....00100
                -- ?? (popcount=2) -> 0
                print(1)
            end
        end
        -- 00100...00001 (popcount=2) -> 1 (popcount=1) -> 0
        print(2)
        return
    end
end
-----
local pop0p1 = pop0 + 1
local pop0m1 = pop0 - 1

local tpnmodP0p1 = {} -- 1<<k mod (pop0+1)
local tpnmodP0m1 = {} -- 1<<k mod (pop0-1)
tpnmodP0p1[0] = 1
tpnmodP0m1[0] = 1
for i=1,N do
    tpnmodP0p1[i] = (tpnmodP0p1[i-1] * 2) % pop0p1
    tpnmodP0m1[i] = (tpnmodP0m1[i-1] * 2) % pop0m1
end
local XmodP0p1 = 0 -- X mod (pop0+1)
local XmodP0m1 = 0 -- X mod (pop0-1)
for i=N,1,-1 do
    local k = N - i
    if Xs[i] == "1" then
        XmodP0p1 = (XmodP0p1 + tpnmodP0p1[k]) % pop0p1
        XmodP0m1 = (XmodP0m1 + tpnmodP0m1[k]) % pop0m1
    end
end
for i=1,N do
    local k = N - i
    if Xs[i] == "0" then
        local op1res = (XmodP0p1 + tpnmodP0p1[k]) % pop0p1
        if op1res == 0 then
            print(1)
        else
            print(f_naive(op1res)+1)
        end
    else
        local op1res = (XmodP0m1 - tpnmodP0m1[k] + pop0m1) % pop0m1
        if op1res == 0 then
            print(1)
        else
            print(f_naive(op1res)+1)
        end
    end
end

Measured memory_bytes: 43516