Верный конь Рустама, Рахш, уже не тот, что раньше. Некогда могущественный и быстрый, Рахш со временем стал слабее. Рустам беспокоится, что если слишком много частей тела Рахша потеряют силу одновременно, Рахш может полностью остановиться. Чтобы поддержать своего спутника, Рустам решает укрепить Рахша, чтобы ни одна часть его тела не стала слишком слабой.
Тело Рахша можно представить в виде последовательности пятен, представленных бинарной строкой $$$s$$$ длины $$$n$$$, где символ $$$0$$$ означает слабое место, а $$$1$$$ — сильное. Цель Рустама — убедиться, что ни один интервал из $$$m$$$ последовательных пятен не является полностью слабым (все пятна обозначены $$$0$$$).
К счастью, Рустам обладает особой способностью под названием Тимар, унаследованной от его матери Рудабе при рождении. С помощью Тимар он может выбрать любой отрезок длины $$$k$$$ и мгновенно усилить его (изменить каждый символ на этом отрезке на $$$1$$$). Ваша задача состоит в том, чтобы определить минимальное число раз, которое Рустаму нужно использовать Тимар, чтобы на теле Рахша не осталось последовательных полностью слабых участков длины $$$m$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le m, k \le n \le 2 \cdot 10^5$$$). Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую из символов $$$s_1s_2 \ldots s_n$$$ ($$$s_i \in \{$$$0,1$$$\}$$$ для всех $$$1 \le i \le n$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите минимальное число раз, которое Рустаму необходимо использовать Тимар, чтобы поддерживать движение Рахша, гарантируя отсутствие последовательных полностью слабых участков длины $$$m$$$.
35 1 1101015 2 1101016 3 2000000
2 0 1
В первом наборе входных данных мы должны применить операцию к каждому символу 0.
Во втором наборе входных данных $$$s$$$ уже удовлетворяет условию.
В третьем наборе входных данных мы можем выполнить операцию над интервалом $$$[3,4]$$$ для получения 001100.
