任何东西都会归零

定义 $ \mathrm{popcount}(n) $ 为 $ n $ 在二进制表示中 '1' 的个数。例如，$ \mathrm{popcount}(3)\ =\ 2,\ \mathrm{popcount}(7)\ =\ 3,\ \mathrm{popcount}(0)\ =\ 0 $。
定义 $ f(n) $ 为将 $ n $ 用 $ \mathrm{popcount}(n) $ 除后取余数替换 $ n $ 的操作次数，直到 $ n $ 变为 $ 0 $ 为止（在这个问题的约束下，可以证明 $ n $ 经过有限次操作后一定会变为 $ 0 $）。
以下是以 $ n=7 $ 为例，经过 2 次操作 $ n $ 变为 0 的过程。

• 因为 $ \mathrm{popcount}(7)=3 $，所以用 3 除 7 后的余数 1 替换 7。
• 因为 $ \mathrm{popcount}(1)=1 $，所以用 1 除 1 后的余数 0 替换 1。
  给定一个二进制表示的 $ N $ 位整数 $ X $。对于满足 $ 1\ \leq\ i\ \leq\ N $ 的整数 $ i $，定义将 $ X $ 的第 $ i $ 位取反后的整数为 $ X_i $。求 $ f(X_1),\ f(X_2),\ \ldots,\ f(X_N) $。

输入从标准输入中以以下形式给出。

$ N $ $ X $

输出 $ N $ 行。第 $ i $ 行输出 $ f(X_i) $ 的值。

样例 #1

样例输入 #1

3
011

样例输出 #1

2
1
1

样例 #2

样例输入 #2

23
00110111001011011001110

样例输出 #2

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

制約

• $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
• $ X $ 是二进制表示的 $ N $ 位的整数（首位不一定是 '1'）

样例解释 #1

• $ X_1 $ 是 7。因为 7 变为 1 再变为 0，所以 $ f(7) = 2 $。
• $ X_2 $ 是 1。因为 1 变为 0，所以 $ f(1) = 1 $。
• $ X_3 $ 是 2。因为 2 变为 0，所以 $ f(2) = 1 $。