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

Тето играет в популярную ритм-игру osu!. Игра может быть описана бинарной строкой$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$ и целым положительным числом $$$k$$$, с которыми будет происходить следующее:

  • Вы выберете некоторые позиции в $$$s$$$ для защиты.
  • Затем для каждого $$$i$$$ ($$$1 \le i \le n$$$) в порядке возрастания Тето может установить $$$s_i$$$ в $$$\mathtt{0}$$$, если все следующие условия истинны:
    • $$$s_i = \mathtt{1}$$$,
    • $$$s_i$$$ не защищен,
    • предыдущие $$$k - 1$$$ элементов не содержат $$$\mathtt{1}$$$. Более формально, $$$\mathtt{1}$$$ не встречается в $$$s_{\max(1, i - k + 1)},\ldots,s_{i - 1}$$$.

Вам не нравится Тето (умолчим по какой причине). Поэтому определите минимальное количество позиций, которые вам нужно защитить, чтобы заставить её оставить $$$s$$$ без изменений.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая только из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.

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

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

Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 1000$$$; $$$2 \le k \le n$$$) — длина $$$s$$$ и $$$k$$$.

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

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

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

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

Пример
Входные данные
9
2 2
11
6 6
100001
5 3
10000
7 2
1010101
7 4
0000001
3 3
010
3 2
011
7 4
1001001
8 3
00000000
Выходные данные
1
1
1
4
1
1
1
1
0
Примечание

Для первого набора входных данных вы можете защитить первый элемент и получить: $$$s = \mathtt{\color{red}{1}1}$$$. Теперь Тето не может изменить $$$s_1$$$, потому что он защищен, и не может изменить $$$s_2$$$, потому что $$$s_1 = \mathtt{1}$$$. Можно доказать, что это оптимально.

Для второго набора входных данных вы можете защитить только первый элемент и получить $$$s = \color{red}{\mathtt{1}}\mathtt{00001}$$$. Тето не может изменить $$$s_1$$$, потому что он защищен, и она не может изменить $$$s_6$$$, потому что $$$\mathtt{1}$$$ встречается в предыдущих $$$k - 1$$$ элементах ($$$\color{blue}{\mathtt{10000}}\mathtt{1}$$$).

Для четвертого набора входных данных вы должны защитить $$$s_1,s_3,s_5,s_7$$$ и получить $$$s = \mathtt{\color{red}{1}0\color{red}{1}0\color{red}{1}0\color{red}{1}}$$$. Можно показать, что это оптимально. Например, если вы не защитите $$$s_3$$$, то Тето может изменить его на $$$\mathtt{0}$$$ ($$$\mathtt{\color{red}{1}\color{blue}{0}10\color{red}{1}0\color{red}{1}}$$$)