B. В горах нет казино
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ из $$$n$$$ чисел и число $$$k$$$. Значение $$$a_i$$$ описывает погоду в $$$i$$$-й день: если в $$$i$$$-й день будет дождь, то $$$a_i = 1$$$, иначе в $$$i$$$-й день будет хорошая погода и $$$a_i = 0$$$.

Жан хочет посетить как можно больше пиков. Один поход на пик занимает ровно $$$k$$$ дней, при этом в каждый из этих дней должна быть хорошая погода ($$$a_i = 0$$$). То есть, формально, можно начать поход в день $$$i$$$ только если все $$$a_j = 0$$$ для всех $$$j$$$ $$$(i \leq j \leq i + k - 1)$$$.

После каждого похода, прежде чем начать следующий, Жан должен взять перерыв не менее одного дня, то есть на следующий день после похода он не сможет снова отправиться в следующий поход.

Найдите максимальное количество пиков, которые сможет посетить Жан.

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

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

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

Во второй строке задано $$$n$$$ чисел $$$a_i$$$ ($$$a_i \in \{0, 1\}$$$), где $$$a_i$$$ обозначает погоду в $$$i$$$-й день.

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

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

Для каждого набора данных выведите одно целое число: максимальное количество походов, которое может совершить Жан.

Пример
Входные данные
5
5 1
0 1 0 0 0
7 3
0 0 0 0 0 0 0
3 1
1 1 1
4 2
0 1 0 1
6 2
0 0 1 0 0 0
Выходные данные
3
2
0
0
2
Примечание

В первом примере:

  • $$$1$$$-й день — хорошая погода, Жан идёт в поход. ($$$a_1 = 0$$$)
  • $$$2$$$-й день — обязательный перерыв.
  • $$$3$$$-й день — снова хорошая погода, Жан идёт во второй поход. ($$$a_3 = 0$$$)
  • $$$4$$$-й день — перерыв.
  • $$$5$$$-й день — хорошая погода, третий поход. ($$$a_5 = 0$$$)
Таким образом, Жан может совершить 3 похода, чередуя каждый из них с обязательным днём отдыха.

Во втором примере:

  • С $$$1$$$ по $$$3$$$ день — три дня хорошей погоды, Жан идёт в поход. ($$$a_1 = a_2 = a_3 = 0$$$)
  • $$$4$$$-й день — обязательный перерыв.
  • С $$$5$$$ по $$$7$$$ день — снова три дня хорошей погоды, Жан идёт во второй поход. ($$$a_5 = a_6 = a_7 = 0$$$)
Всего Жан совершает 2 похода.

В третьем примере:

  • Нет ни одного дня с хорошей погодой ($$$a_i = 1$$$ для всех $$$i$$$)
Жан не может совершить ни одного похода. Ответ: 0