题目描述

定义 $\\mathrm{popcount}(n)$ 为 $n$ 的二进制表示中出现的 1 的个数。例如，$\\mathrm{popcount}(3) = 2$，$\\mathrm{popcount}(7) = 3$，$\\mathrm{popcount}(0) = 0$。

定义 $f(n)$ 为重复以下操作直到 $n$ 变为 $0$ 时所进行的次数：将 $n$ 除以 $\\mathrm{popcount}(n)$，并用余数替换 $n$。（在本问题的约束条件下，可以证明 $n$ 经过有限次操作后总会变为 $0$。）

例如，当 $n=7$ 时，经过两次操作后变为 $0$，具体过程如下：

• $\\mathrm{popcount}(7)=3$，所以我们将 $7$ 除以 $3$，并用余数 $1$ 替换它。
• $\\mathrm{popcount}(1)=1$，所以我们将 $1$ 除以 $1$，并用余数 $0$ 替换它。

给定一个具有 $N$ 位的二进制整数 $X$。对于每个满足 $1 \\leq i \\leq N$ 的整数 $i$，设 $X_i$ 是把 $X$ 的从左往右第 $i$ 位取反后得到的结果。求 $f(X_1), f(X_2), \\ldots, f(X_N)$。

约束条件

• $1 \\leq N \\leq 2 \\times 10^5$
• $X$ 是一个有 $N$ 位的二进制整数，可能存在前导零。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $X$

输出

输出 $N$ 行。第 $i$ 行应包含值 $f(X_i)$。

示例输入1

3
011

示例输出1

2
1
1

• $X_1 = 7$，变化过程如下：$7 \\rightarrow 1 \\rightarrow 0$。因此，$f(7) = 2$。
• $X_2 = 1$，变化过程如下：$1 \\rightarrow 0$。因此，$f(1) = 1$。
• $X_3 = 2$，变化过程如下：$2 \\rightarrow 0$。因此，$f(2) = 1$。

示例输入2

23
00110111001011011001110

示例输出2

2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3