E. К-периодичная гирлянда
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана гирлянда, состоящая из $$$n$$$ ламп. Состояния ламп описываются строкой $$$s$$$ длины $$$n$$$. $$$i$$$-й символ строки $$$s_i$$$ равен '0', если $$$i$$$-я лампа выключена, или '1', если $$$i$$$-я лампа включена. Вам также задано положительное целое число $$$k$$$.

За один ход вы можете выбрать одну лампу и изменить ее состояние (то есть включить ее, если она выключена, и наоборот).

Гирлянда называется $$$k$$$-периодичной, если расстояние между каждой парой соседних включенных ламп равно в точности $$$k$$$. Рассмотрим случай $$$k=3$$$. Тогда гирлянды «00010010», «1001001», «00010» и «0» являются хорошими, а гирлянды «00101001», «1000001» и «01001100» не являются хорошими. Заметьте, что гирлянда не является цикличной, то есть первая включенная лампа не идет после последней включенной лампы и наоборот.

Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы получить $$$k$$$-периодичную гирлянду из заданной.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 25~ 000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^6; 1 \le k \le n$$$) — длину $$$s$$$ и необходимый период. Вторая строка набора тестовых данных содержит строку $$$s$$$, состоящую из $$$n$$$ символов '0' и '1'.

Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$10^6$$$ ($$$\sum n \le 10^6$$$).

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

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

Пример
Входные данные
6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0
Выходные данные
1
2
5
4
0
0