B. Бесконечные префиксы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана строка $$$s$$$ длины $$$n$$$, состоящая только из 0 и 1. Построим бесконечную строку $$$t$$$ как конкатенацию бесконечного числа строк $$$s$$$, или $$$t = ssss \dots$$$ Например, если $$$s =$$$ 10010, то $$$t =$$$ 100101001010010...

Посчитайте количество префиксов $$$t$$$ с балансом равным $$$x$$$. Баланс строки $$$q$$$ равен $$$cnt_{0, q} - cnt_{1, q}$$$, где $$$cnt_{0, q}$$$ — это количество вхождений 0 в $$$q$$$, а $$$cnt_{1, q}$$$ — количество вхождений 1 в $$$q$$$. Количество таких префиксов может быть бесконечно: в таком случае, вы должны определить это.

Префикс — строка, состоящая из нескольких первых букв заданной строки, без изменения их порядка. Пустой префикс тоже является префиксом. Например, у строки «abcd» пять префиксов: пустая строка, «a», «ab», «abc» и «abcd».

Входные данные

В первой строке задано единственное целое число $$$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$$$.

Выходные данные

Выведите $$$T$$$ чисел — по одному на набор входных данных. Для каждого набора выведите количество префиксов или $$$-1$$$, если таких префиксов бесконечное количество.

Пример
Входные данные
4
6 10
010010
5 3
10101
1 0
0
2 0
01
Выходные данные
3
0
1
-1
Примечание

В первом наборе есть 3 хороших префикса строки $$$t$$$: длины $$$28$$$, $$$30$$$ и $$$32$$$.