题目描述

给定一个恰好由 $n$ 位组成的二进制数（可能有前导零）。例如，当 $n = 5$ 时，数字 $6$ 的二进制表示为 $00110$，当 $n = 4$ 时，数字 $9$ 的二进制表示为 $1001$。

现在固定一个整数 $i$，满足 $1 \le i \le n$。每次操作你可以交换二进制表示中任意两个相邻的位。你的目标是找出使该数能被 $2^i$ 整除所需的最少操作次数，或者判断是否不可能实现。

请注意，对于每个 $1 \le i \le n$，你都需要独立地解决这个问题。

输入格式

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

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

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

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

输出格式

对于每个测试用例，对于每个 $1 \le i \le n$，输出使该数能被 $2^i$ 整除所需的最少操作次数，或者如果无法实现则输出 $-1$。

说明/提示

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

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

在第三个测试用例中，初始数字为 $2$。对于 $i=1$，无需进行任何操作，因为初始数字已经能被 $2$ 整除。对于 $i=2$，可以通过一次操作交换前两位（得到二进制 $100$，即十进制 $4$）。对于 $i=3$，无解。

由 ChatGPT 4.1 翻译

样例

6
1
1
2
01
3
010
5
10101
7
0000111
12
001011000110

-1 
1 -1 
0 1 -1 
1 3 -1 -1 -1 
3 6 9 12 -1 -1 -1 
0 2 4 6 10 15 20 -1 -1 -1 -1 -1