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

Поликарп с друзьями хочет сходить в новый ресторан. Ресторан представляет из себя $$$n$$$ столиков, расставленных вдоль прямой. За некоторыми столиками уже сидят люди. Столики пронумерованы от $$$1$$$ до $$$n$$$ в порядке слева направо. Состояние ресторана описывается строкой длины $$$n$$$, которая содержит символы '1' (столик занят) и '0' (столик свободен).

Правила ресторана запрещают людям садиться на расстоянии $$$k$$$ или меньше друг от друга. То есть, если человек сидит за столиком номер $$$i$$$, то все столики с номерами от $$$i-k$$$ до $$$i+k$$$ (кроме $$$i$$$-го) должны быть свободны. Иными словами, разница (то есть модуль разности) номеров между любыми двумя занятыми столиками должна быть строго больше $$$k$$$.

Например, если $$$n=8$$$ и $$$k=2$$$, то:

  • строки «10010001», «10000010», «00000000», «00100000» соответствуют правилам ресторана;
  • строки «10100100», «10011001», «11111111» не соответствуют правилам ресторана, так как в каждой из них есть пара единиц на расстоянии меньшем или равном $$$k=2$$$.

В частности, если состояние ресторана описывается строкой без единиц или строкой с одной единицей, то требование ресторана выполнено.

Вам задана бинарная строка $$$s$$$, которая описывает текущее состояние ресторана. Гарантируется, что для строки $$$s$$$ правила ресторана выполнены.

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

Например, если $$$n=6$$$, $$$k=1$$$, $$$s=$$$ «100010», то ответ на задачу будет $$$1$$$, так как есть только один свободный столик на позиции $$$3$$$, который можно занять в соответствии с правилами ресторана.

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

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

Каждый набор начинается со строки, в которой записано два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2\cdot 10^5$$$) — количество столиков в ресторане и минимальное разрешенное расстояние между двумя людьми.

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

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

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

Для каждого тестового набора выведите одно целое число — количество столиков, которые можно дополнительно занять, чтобы не нарушить правила ресторана. Если дополнительных столиков занять нельзя, то, очевидно, надо вывести $$$0$$$.

Пример
Входные данные
6
6 1
100010
6 2
000000
5 1
10101
3 1
001
2 2
00
1 1
0
Выходные данные
1
2
0
1
1
1
Примечание

Первый набор тестовых данных разобран в условии.

Во втором наборе тестовых данных ответ $$$2$$$, так как можно выбрать первый и шестой столики.

В третьем наборе тестовых данных нельзя занять никакой свободный столик, не нарушив правила ресторана.