A13223 | Infinite Prefixes

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.