using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace debug
{
class main
{
static void Main(string args)
{
//問題クラスを展開
ProgramD a = new ProgramD();
a.main();//実行する
}
}
//エイシング
class ProgramA
{
public void main()
{
//入力
string s = Console.ReadLine().Split(' ');
int h = int.Parse(s[0]);
int w = int.Parse(s[1]);
int k = int.Parse(s[2]);
int count = 0;
//hからwでkで割れるか調べる
for(int i = h;i <= w;i++)
{
if (i % k == 0)
count++;
}
//答え出力
Console.WriteLine(count);
}
}
class ProgramB
{
public void main()
{
//入力
int n = int.Parse(Console.ReadLine());
string s = Console.ReadLine().Split(' ');
int count = 0;
//奇数番目のみ検索して、奇数かどうか見る
for(int i = 0; i < n;i = i + 2)
{
if (int.Parse(s[i]) % 2 == 1)
count++;
}
//答え出力
Console.WriteLine(count);
}
}
class ProgramC
{
public void main()
{
//入力
int n = int.Parse(Console.ReadLine());
int ans = new int[n];
//(x,y,z)組み合わせを全探索最大でも1-100までの間しかないことに注目
for(int x = 1;x <= 100;x++)
for (int y = 1; y <= 100; y++)
for (int z = 1; z <= 100; z++)
{
long temp = x * x + y * y + z * z + x * y + x * z + y * z;
if (temp <= n)
ans[temp - 1]++;
}
//答え出力
for(int i = 0;i < n;i++)
Console.WriteLine(ans[i]);
}
}
class ProgramD
{
public void main()
{
//入力
long n = long.Parse(Console.ReadLine());
string s = Console.ReadLine();
int count = 0;
long num = 0;
long num2 = 0;
//あらかじめ1の数は数える
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
count++;
}
//popcount=0のとき
if (count == 0)
{
for (int i = 0; i < n; i++)
Console.WriteLine("1");
return;
}
//popcount=1のとき
if (count == 1)
{
if (s[(int)n - 1] == '1')
{
for (int i = 0; i < n; i++)
{
if (i == n - 1)
Console.WriteLine("0");
else
Console.WriteLine("2");
}
}
else
{
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
Console.WriteLine("0");
else if(i == n -1)
Console.WriteLine("2");
else
Console.WriteLine("1");
}
}
return;
}
//popcount±1野ときをそれぞれ求めておく
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
{
num += modpow(2, n - 1 - i, count -1);
num2 += modpow(2, n - 1 - i, count + 1);
}
}
for (int i = 0; i < n; i++)
{
long temp = 0;
//ビット反転後の数を求める
if (s[i] == '1')
{
temp = num;
temp -= modpow(2, n - 1 - i, count - 1);
temp %= count - 1;
}
else
{
temp = num2;
temp += modpow(2, n - 1 - i, count + 1);
temp %= count + 1;
}
//1以下目の操作終了
long ans = 1;
//0になるまで操作
while(temp != 0)
{
long t = 0;
long t2 = temp;
//2進数で1の数を出す
while (temp != 0)
{
t += temp % 2;
temp /= 2;
}
temp = t2 % t;
ans++;//一回の操作はここで終わり
}
//操作回数を出力
Console.WriteLine(ans);
}
}
//繰り返し二乗法
static long modpow(long a, long n, long MOD)
{
if (n == 0)
return 1;
if (n % 2 == 0)
{
long temp = modpow(a, n / 2, MOD);
return temp * temp % MOD;
}
return a * modpow(a, n - 1, MOD) % MOD;
}
}
}
