题目描述

题目翻译：

给定一个长度为 n 的二进制字符串 s，其中 0 表示弱点，1 表示强点。需要确保任意长度为 m 的连续区间内至少有一个强点。可以使用一种特殊能力 Timar，它能将任意长度为 k 的区间内的所有点变为强点（即 1）。求解需要使用 Timar 的最小次数，使得字符串 s 中任意长度为 m 的连续区间都至少包含一个 1。

输入格式

• 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
• 每个测试用例的第一行包含三个整数 n, m, k（1 ≤ m, k ≤ n ≤ 2*10^5）。
• 每个测试用例的第二行包含一个长度为 n 的二进制字符串 s。

输出格式

• 对于每个测试用例，输出需要使用 Timar 的最小次数。

样例

3
5 1 1
10101
5 2 1
10101
6 3 2
000000

2
0
1