#include <bits/stdc++.h>
            #include <ext/pb_ds/assoc_container.hpp>
            #include <ext/pb_ds/tree_policy.hpp>
            using namespace std;
            using namespace __gnu_pbds;
            #define rep(i,a,b) for(ll i =a; i<b;++i)
            #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            #define nl "\n"
            #define pb push_back
            #define F first
            #define S second
            #define print(a)       for(auto x : a) cout << x << " "; cout << endl
            #define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
            #define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
            #define mk(x,y)  make_pair(x,y)
            typedef long long int ll;
            const ll N =  5e5+ 5 ;
         ///   const ll mod = 1e9+7;
            const ll inf = 1e18;
            ll   n  , m , a[N] , h[N]  , k  , b , c , q , x,y;
    ll pow_mod_m(ll a , ll n, ll mod)
    {
        if(mod <= 0)
            return 0;
        if(n < 0)
            return 0;
        if(!n)
            return 1;
        ll pt =  pow_mod_m(a,n/2, mod);
        pt *= pt , pt %= mod;
        if(n&1)
            pt *= a  ,pt %= mod;
        return pt;
    }

    int main()
    {
         IOS;
         int ts =1;
       ///  cin >> ts;
         while(ts--)
         {
            cin >> n;
            string s;
            cin >> s;
            ll tot = 0 , popcnt = 0 ;
            reverse(s.begin() , s.end());
            for(int i = 0 ;i < n; i++)
            {
                if(s[i] == '1')
                {
                    popcnt++;
                }
            }
            ll plusone =  0 , minusone = 0;
            for(int i = n-1; i>=0 ; i--)
            {
                if(s[i] == '1')
                {
                    plusone += pow_mod_m(2 , i , popcnt+1);
                    plusone %= (popcnt+1);
                    minusone +=pow_mod_m(2 , i , popcnt-1);
                    if(popcnt -1)
                    minusone %= (popcnt-1);
                }
            }
            ll z ;
            for(int i = n-1; i>=0 ;i--)
            {
                ll cnt =0 ;
                ll mone = minusone , pone = plusone;
                if(s[i] == '1')
                {
                    mone -= pow_mod_m(2,i , popcnt-1);
                    mone += popcnt-1;
                    if(popcnt-1 > 0 )
                    {
                        cnt++;
                        mone %= (popcnt-1);
                    }
                    z = mone;
                    while(z)
                    {
                        ll p = __builtin_popcount(z);
                        z %= p;
                        cnt++;
                    }
                }
                else
                {
                    pone += pow_mod_m(2 , i , popcnt+1);
                    pone %= (popcnt+1);
                    cnt++;
                    z = pone;
                    while(z)
                    {
                        ll p = __builtin_popcount(z);
                        z %= p;
                        cnt++;
                    }
                }
                cout << cnt << nl;
            }
         }
    }


Measured memory_bytes: 3688