B. Infinite Prefixes
math; strings
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.
In the first test case, there are 3 good prefixes of \(t\): with length \(28\), \(30\) and \(32\).