CF1295B.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".

给你一个长度为 $n$ 的字符串 $s$，它仅由字符 0 和 1 组成。你通过无限次拼接 $s$ 构造一个无限长字符串 $t$，即 $t = ssss \dots$。例如，若 $s =$ 10010，则 $t =$ 100101001010010...。

请计算 $t$ 的所有前缀中，平衡值等于 $x$ 的前缀个数。字符串 $q$ 的平衡值定义为 $cnt_{0, q} - cnt_{1, q}$，其中 $cnt_{0, q}$ 表示 $q$ 中 0 的出现次数，$cnt_{1, q}$ 表示 $q$ 中 1 的出现次数。满足条件的前缀个数可能为无穷；若是如此，你必须明确指出这一点。

前缀指由给定字符串的最前面若干个字符（顺序不变）组成的字符串；空字符串也是一个合法的前缀。例如，字符串 "abcd" 共有 5 个前缀：空字符串、"a"、"ab"、"abc" 和 "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$.

第一行包含一个整数 $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$。

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.

输出 $T$ 个整数——每个测试用例输出一个整数。对于每个测试用例，输出满足条件的前缀个数；若满足条件的前缀有无穷多个，则输出 $-1$。

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

在第一个测试用例中，$t$ 有 3 个好前缀，其长度分别为 $28$、$30$ 和 $32$。