CF1884B.Haunted House

You are given a number in binary representation consisting of exactly $n$ bits, possibly, with leading zeroes. For example, for $n = 5$ the number $6$ will be given as $00110$, and for $n = 4$ the number $9$ will be given as $1001$.

Let's fix some integer $i$ such that $1 \le i \le n$. In one operation you can swap any two adjacent bits in the binary representation. Your goal is to find the smallest number of operations you are required to perform to make the number divisible by $2^i$, or say that it is impossible.

Please note that for each $1 \le i \le n$ you are solving the problem independently.

你将得到一个恰好由 $n$ 位二进制数字组成的数（可能包含前导零）。例如，当 $n = 5$ 时，数字 $6$ 表示为 $00110$；当 $n = 4$ 时，数字 $9$ 表示为 $1001$。

现固定某个整数 $i$，满足 $1 \le i \le n$。在一次操作中，你可以交换二进制表示中任意两个相邻的比特位。你的目标是：求出使该数能被 $2^i$ 整除所需的最少操作次数；若不可能实现，则说明其不可行。

请注意：对每个满足 $1 \le i \le n$ 的 $i$，你均需独立求解该问题。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the binary representation of the number.

The second line of each test case contains a string of length $n$, consisting of $0$ and $1$, — the binary representation of the number.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）——该数字二进制表示的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串，仅由字符 $0$ 和 $1$ 组成——即该数字的二进制表示。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, for each $1 \le i \le n$ output the smallest number of operations required to make the number divisible by $2^i$, or output $-1$ if it is impossible.

对于每个测试用例，对每个 $1 \le i \le n$，输出使该数能被 $2^i$ 整除所需的最少操作次数；若不可能，则输出 $-1$。

In the first test case, we cannot swap any elements, and the number $1$ is not divisible by $2$.

In the second test case, the initial number is $1$. It is not divisible by $2$, but if we perform the operation, then we obtain the number with binary representation $10$, which is equal to $2$ in decimal representation, thus, it is divisible by $2$. But this number is not divisible by $4$ and we cannot obtain any other number using the operations.

In the third test case, the initial number is $2$. For $i = 1$ we do not have to perform any operations since the initial number is divisible by $2$. For $i = 2$ we can perform one operation swapping the first two bits (we would obtain $100$ in binary representation, which corresponds to number $4$). There is no answer for $i = 3$.

在第一个测试用例中，我们无法交换任何元素，且数字 $1$ 不能被 $2$ 整除。

在第二个测试用例中，初始数字为 $1$。它不能被 $2$ 整除，但如果执行一次操作，则得到二进制表示为 $10$ 的数字，其十进制值为 $2$，因此可被 $2$ 整除。但该数字不能被 $4$ 整除，且通过所允许的操作无法得到其他数字。

在第三个测试用例中，初始数字为 $2$。当 $i = 1$ 时，无需执行任何操作，因为初始数字已可被 $2$ 整除；当 $i = 2$ 时，可执行一次操作，交换前两位（得到二进制表示 $100$，对应十进制数 $4$）；当 $i = 3$ 时，无解。