Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Infinite Prefixes

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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".

Input

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$$$.

Output

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.

Example

Input

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

Output

3 0 1 -1

Note

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/04/2020 19:05:36 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|