给定字符串 $$$s$$$,长度为 $$$n$$$,由 0 和 1 组成。您构建一个无限字符串 $$$t$$$ 作为无限数量字符串 $$$s$$$ 的串联,或 $$$t = ssss \dots$$$ 例如,如果 $$$s =$$$ 10010,则 $$$t =$$$ 100101001010010...
计算余额等于$$$x$$$的$$$t$$$的前缀数量。某个字符串 $$$q$$$ 的余额等于 $$$cnt_{0, q} - cnt_{1, q}$$$,其中 $$$cnt_{0, q}$$$ 是 $$$q$$$ 中 0 出现的次数,$$$cnt_{1, q}$$$ 是 $$$q$$$ 中 1 出现的次数。此类前缀的数量可以是无限的;如果是这样,你就必须这么说。
前缀是由给定字符串的几个首字母组成的字符串,没有任何重新排序。空前缀也是有效前缀。例如,字符串“abcd”有 5 个前缀:空字符串、“a”、“ab”、“abc”和“abcd”。
输入
第一行包含单个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 测试用例的数量。
接下来的 $$$2T$$$ 行包含测试用例的描述 - 每个测试用例两行。第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$-10^9 \le x \le 10^9$$$) — 分别是字符串 $$$s$$$ 的长度和所需的余额。
第二行包含二进制字符串 $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{\text{0}, \text{1}\}$$$)。
保证$$$n$$$的总和不超过$$$10^5$$$。
输出
打印 $$$T$$$ 整数 — 每个测试用例一个。对于每个测试用例,打印前缀的数量,如果存在无限数量的此类前缀,则打印 $$$-1$$$ 。
示例
输入 #1
4 6 10 010010 5 3 10101 1 0 0 2 0 01
输出 #1
3 0 1 -1
注意
在第一个测试用例中,$$$t$$$ 有 3 个好的前缀:长度为 $$$28$$$、$$$30$$$ 和 $$$32$$$。