#pragma optimize("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
// #include<iomanip>
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pii;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fo(i,a,b) for(ll i = a; i<=b;i+=1)
#define rf(i,a,b)  for(ll i=a;i>=b;i--)
#define vll vector<ll>
#define sz(a) ll(a.size())
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front 
#define MAXN 100010
#define N 100010
#define MOD 1000000007
#define mod 998244353
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define nl '\n'
#define MS(x,y) fill_n(*x, sizeof x / sizeof **x, y);
#define mem(x,y) memset(x,y,sizeof(x));
#define INF 1000000000000000000
#define IO                 \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0);

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
static_assert(D >= 1, "Vector dimension must be greater than zero!");
template<typename... Args>
	Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
	}
};
template<typename T>
struct Vec<1, T> : public vector<T> {
	Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
	}
};

ll modpower(ll x, ll y,ll p)
{
    ll res = 1;     // Initialize result
    x = x % p;
    if (y==0)return 1;
    if(x==0)return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1; // y = y/2
        x = (x*x) % p;  // Change x to x^2
    }
    return res;
}
ll power(ll x, ll y)
{
    ll res = 1;     // Initialize result
    x = x ;
    if (y==0)return 1;
    if(x==0)return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x);
        y = y>>1; // y = y/2
        x = (x*x);  // Change x to x^2
    }
    return res;
}
// int gcd(int a, int b) { if (a == 0)return b;return gcd(b % a, a);}

ll modinv(ll a,ll p){return modpower(a,p-2,p);}

const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};

long long safe_sqrt(long long n) {
    long long res = sqrt((long double) n);
    if (res*res == n) return res;
    const long double eps = 1e-8;
    if ((long double)(res+1)*(res+1) < n + eps) return res+1;
    if ((long double)res*res + eps > n) return res-1;
    return res;
}   
// (a+b-1)/b for ceil
void solve(){
    ll n;
    cin>>n;
    vector<char> v;
    ll cnt = 0;
    // deb(7)
    f(i,0,n){
        char c;
        cin>>c;
        v.pb(c);
        if (c=='1')
        {
            cnt++;
        }
    }
    // deb(1)
    if (cnt==0)
    {
        // deb(2)
        f(i,0,n){
            cout<<1<<nl;
        }
        return;
    }
    else if (cnt==1)
    {
        // deb(4)
        vll ans(n,0);
        f(i,0,n){
            if(v[i]=='1'){// popcnt = 0
                ans[i] = 0;
            }
            else {// popcount = 2
                if (i==n-1)
                {
                    ans[i] = 2;
                }
                else ans[i] = 1;
            }
        }
        f(i,0,n){
            cout<<ans[i]<<nl;
        }
        return;
    }
    ll theta1 = 0, theta2 = 0;
    vector<char> p(all(v));
    reverse(all(p));
    rf(i,n-1,0){
        if(p[i]=='1'){
            (theta1+=modpower(2,i,cnt-1))%=(cnt-1);
        }
    }
    rf(i,n-1,0){
        if(p[i]=='1'){
            (theta2+=modpower(2,i,cnt+1))%=(cnt+1);
        }
    }
    vll ans(n,0);
    rf(i,n-1,0){
        // deb(p[i])
        if(p[i]=='1'){
            // theta1
            // deb(((theta1 + cnt - 1 - modpower(2,i,cnt - 1))))
            ll x = (theta1 + cnt - 1 - modpower(2,i,cnt - 1))%(cnt-1);
            ll steps = 1;
            ll div;
            ll num = x;
            div = 0;
            while(num>0){
                if (num%2)
                {
                    div++;
                }
                num/=2;
            }
            while(x>0){
                x = x%(div);
                ll num = x;
                div = 0;
                while(num>0){
                    if (num%2)
                    {
                        div++;
                    }
                    num/=2;
                }
                steps++;
            }
            ans[n-1-i] = steps;
        }
        else {// theta2
            ll x = (theta2 + modpower(2,i,cnt + 1))%(cnt + 1);
            ll steps = 1;
            ll num = x;
            ll div;
            div = 0;
            while(num>0){
                if (num%2)
                {
                    div++;
                }
                num/=2;
            }
            while(x>0){
                x = x%(div);
                ll num = x;
                div = 0;
                while(num>0){
                    if (num%2)
                    {
                        div++;
                    }
                    num/=2;
                }
                steps++;
            }
            ans[n-1-i] = steps;
        }
    }
    f(i,0,n){
        cout<<ans[i]<<nl;
    }
    return ;
}
int main()
{
    IO;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // #endif
    int T = 1;
    // cin >> T;
    f(c, 0, T){
        solve();
    }
    return 0;
}//multiset m make_pair make_tuple  tuple<int,int,int> continue resize insert count size else true isValid second first false erase double priority_queue 
//cout<<setprecision(12); push_back pop_back pop_front push_front  lower_bound upper_bound  reverse

Measured memory_bytes: 5224