D. Исправление бинарной строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная строка $$$s$$$ длины $$$n$$$, состоящая из нулей и единиц. Вы можете сделать следующую операцию ровно один раз:

  1. Выбрать целое число $$$p$$$ ($$$1 \le p \le n$$$).
  2. Перевернуть подстроку $$$s_1 s_2 \ldots s_p$$$. После выполнения этого шага строка $$$s_1 s_2 \ldots s_n$$$ превратится в строку $$$s_p s_{p-1} \ldots s_1 s_{p+1} s_{p+2} \ldots s_n$$$.
  3. После этого сделать циклический сдвиг строки $$$s$$$ влево $$$p$$$ раз. После выполнения этого шага изначальная строка $$$s_1s_2 \ldots s_n$$$ превратится в строку $$$s_{p+1}s_{p+2} \ldots s_n s_p s_{p-1} \ldots s_1$$$.

Например, если применить операцию к строке 110001100110 при $$$p=3$$$, то после второго шага получится строка 011001100110, а после третьего шага 001100110011.

Строка $$$s$$$ называется $$$k$$$-правильной, если выполняются два условия:

  • $$$s_1=s_2=\ldots=s_k$$$;
  • $$$s_{i+k} \neq s_i$$$ для любого $$$i$$$ ($$$1 \le i \le n - k$$$).

Например, при $$$k=3$$$ строки 000, 111000111 и 111000 являются $$$k$$$-правильными, а строки 000000, 001100 и 1110000 нет.

Дано целое число $$$k$$$, которое является делителем $$$n$$$. Найдите целое число $$$p$$$ ($$$1 \le p \le n$$$), после выполнения операции с которым строка $$$s$$$ станет $$$k$$$-правильной или определите, что это невозможно. Обратите внимание, что если строка изначально является $$$k$$$-правильной, то к ней всё равно нужно применить ровно одну операцию.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n$$$, $$$2 \le n \le 10^5$$$) — длина строки $$$s$$$ и значение $$$k$$$. Гарантируется, что $$$k$$$ является делителем $$$n$$$.

Вторая строка каждого набора содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую из символов 0 и 1.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — значение $$$p$$$, чтобы сделать строку $$$k$$$-правильной, или $$$-1$$$, если это невозможно.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
7
8 4
11100001
4 2
1110
12 3
111000100011
5 5
00000
6 1
101001
8 4
01110001
12 2
110001100110
Выходные данные
3
-1
7
5
4
-1
3
Примечание

В первом наборе входных данных, если применить операцию при $$$p=3$$$, то после второго шага операции строка станет равна 11100001, а после третьего 00001111. Эта строка является $$$4$$$-правильной.

Во втором наборе входных данных можно показать, что не существует операции, после которой строка становится $$$2$$$-правильной.

В третьем наборе входных данных, если применить операцию при $$$p=7$$$, то после второго шага операции строка станет равна 100011100011, а после третьего 000111000111. Эта строка является $$$3$$$-правильной.

В четвертом наборе входных данных после операции c любым $$$p$$$ строка является $$$5$$$-правильной.