#include<bits/stdc++.h>
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pb           push_back
#define ff           first
#define ss           second
#define gcd(a, b)    __gcd(a, b)
#define lcm(a, b)    ((a)*((b)/gcd(a,b)))
#define all(v)       v.begin(),v.end()
#define rall(v)      v.rbegin(),v.rend()
#define lllim        2147483648
#define Pi           2*acos(0.0)
#define pii          pair<int,int>
#define pll          pair<ll,ll>
#define mem(a,b)     memset(a, b, sizeof(a))
#define fill_(a,b)   fill(a,a+n,b);
#define MOD          1000000007
#define fast_cin     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define filein       freopen("input.txt","r", stdin)
#define D(x)         cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define case         int t,cas=1;cin>>t;while(t--)
#define rep(i,a,n)   for(int i=a;i<n;i++)
#define rev(i,n,a)   for(int i=n;i>=a;i--)
#define sim          template<class T

/*------------------------------Graph Moves----------------------------*/
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]= {+0,+0,+1,-1,-1,+1,-1,+1};  // Kings Move
//const int fy[]= {-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/


sim > void read(T& a) {
    std::cin>>a;
}
sim > void read(T& a, T& b) {
    std::cin>>a>>b;
}
sim > void read(T& a,T& b, T& c) {
    std::cin>>a>>b>>c;
}

sim > void readvec( std::vector<T>& v, const int n) {
    rep(i,0,n) {
        T p;
        std::cin>>p;
        v.pb(p);
    }
}

using namespace std;
using namespace __gnu_pbds;


ll bigmod(ll a, ll b, ll m)
{
    if(b==0) return 1;
    if(b==1) return a;

    if(b%2)
    {
        ll res=bigmod(a,b/2,m)%m;
        return ((((res%m)*(res%m))%m)*(a))%m;
    }
    else
    {
        ll res=bigmod(a,b/2,m)%m;
        return (((res%m)*(res%m))%m);
    }
}

const int maxn=200005;
int dp[maxn];

void solve()
{
	int n;
	string s;
	cin>>n>>s;
	
	int ans[n+2]={0};
	
	int cnt=0,cntplus=0,cntminus=0;
	
	rep(i,0,n)
	{
		cnt+=(s[i]=='1');
	}
	
	cntplus=cnt+1;
	cntminus=cnt-1;
	
	ll sumcnt=0,sumplus=0,summinus=0;
	//D(cntplus);
	//D(cntminus);
	
	rep(i,0,n)
	{
		if(s[(n-1-i)]=='1')
		{
			//cnt1;
			sumcnt+=bigmod(2,i,cnt);
			sumplus+=bigmod(2,i,cntplus);
			if(cntminus>0)
			summinus+=bigmod(2,i,cntminus);
			sumplus%=cntplus;
			if(cntminus>0)
			summinus%=cntminus;
			
		  //  cout<<sumplus<<" "<<summinus<<" "<<bigmod(2,i,cntplus)<<' '<<bigmod(2,i,cntminus)<<endl;
		}
		
	}
	
	//cout<<sumplus<<" "<<summinus<<endl;
	
	for(int i=0;i<n;i++)
	{
		if(s[i]=='1')
		{
			ll res=summinus;
			
			if(cntminus<=0) continue;
			
			res-=bigmod(2,n-1-i,cntminus);
			res%=cntminus;
			res+=cntminus;
			res%=cntminus;
			//D(res);
			ans[i]=dp[res];
		}
		else
		{
			ll res=sumplus;
			res+=bigmod(2,n-1-i,cntplus);
			//D(res);
			
			//res+=cntplus;
			res%=cntplus;
			//D(res);
			ans[i]=dp[res];
		}
		ans[i]+=1;
		
	}
	
	
	for(int i=0;i<n;i++)
	{
		cout<<ans[i]<<endl;
	}


}


int main()
{
    fast_cin;
    
    dp[0]=0;
    dp[1]=1;
    
    for(int i=2;i<maxn;i++)
    {
		int cnt=0;
		int num=i;
		while(num)
		{
			cnt+=num&1;
			num>>=1;
		}
		
		
		dp[i]=1+dp[i%cnt];
	}
	//D(dp[15]);
    

//case
    {
        // cout<<"Case "<<cas++<<": ";
        solve();

    }

    return 0;
}


Measured memory_bytes: 5276