给你一个二进制表示的数字,由 $$$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
6 1 1 2 01 3 010 5 10101 7 0000111 12 001011000110
输出 #1
-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
注意
在第一个测试用例中,我们无法交换任何元素,并且数字 $$$1$$$ 不能被 $$$2$$$ 整除。
在第二个测试用例中,初始编号为$$$1$$$。它不能被$$$2$$$整除,但如果我们进行运算,则得到二进制表示的数$$$10$$$,它等于十进制表示的$$$2$$$,因此它可以被$$$2$$$整除。但这个数字不能被 $$$4$$$ 整除,并且我们无法使用该操作获得任何其他数字。
在第三个测试用例中,初始数字是$$$2$$$。对于$$$i = 1$$$,我们不必执行任何操作,因为初始数字可以被$$$2$$$整除。对于$$$i = 2$$$,我们可以执行一个交换前两位的操作(我们将获得二进制表示的$$$100$$$,对应于数字$$$4$$$)。 $$$i = 3$$$ 没有答案。