Infinite Prefixes

题意翻译

给定一个长度为 $n$ 的 $01$ 串 $s$，将它无限复制拼接得到一个无限长的 $01$ 串 $t=ssssss\cdots$，对于 $t$ 的某个前缀定义它的权值为 $0$ 的个数减去 $1$ 的个数，求权值为 $x$ 的前缀的个数，如果无穷多输出 $-1$。

题目描述

You are given string $ s $ of length $ n $ consisting of 0-s and 1-s. You build an infinite string $ t $ as a concatenation of an infinite number of strings $ s $ , or $ t = ssss \dots $ For example, if $ s = $ 10010, then $ t = $ 100101001010010... Calculate the number of prefixes of $ t $ with balance equal to $ x $ . The balance of some string $ q $ is equal to $ cnt_{0, q} - cnt_{1, q} $ , where $ cnt_{0, q} $ is the number of occurrences of 0 in $ q $ , and $ cnt_{1, q} $ is the number of occurrences of 1 in $ q $ . The number of such prefixes can be infinite; if it is so, you must say that. A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".

输入输出格式

输入格式

The first line contains the single integer $ T $ ( $ 1 \le T \le 100 $ ) — the number of test cases. Next $ 2T $ lines contain descriptions of test cases — two lines per test case. The first line contains two integers $ n $ and $ x $ ( $ 1 \le n \le 10^5 $ , $ -10^9 \le x \le 10^9 $ ) — the length of string $ s $ and the desired balance, respectively. The second line contains the binary string $ s $ ( $ |s| = n $ , $ s_i \in \{\text{0}, \text{1}\} $ ). It's guaranteed that the total sum of $ n $ doesn't exceed $ 10^5 $ .

输出格式

Print $ T $ integers — one per test case. For each test case print the number of prefixes or $ -1 $ if there is an infinite number of such prefixes.

输入输出样例

输入样例 #1

4
6 10
010010
5 3
10101
1 0
0
2 0
01

输出样例 #1

3
0
1
-1

说明

In the first test case, there are 3 good prefixes of $ t $ : with length $ 28 $ , $ 30 $ and $ 32 $ .