今天您有 $$$n$$$ 课程,编号从 $$$1$$$ 到 $$$n$$$。
这些类由长度为 $$$n$$$ 的二进制字符串$$$^{\text{*}}$$$ $$$s$$$ 描述。我们称类为$$$i$$$ 重要 当且仅当 $$$s_i = \mathtt 1$$$。对于每个 重要 班上,你 必须 保持清醒并聆听。
您非常累,希望在尽可能多的课程中睡觉。然而,入睡需要时间。如果你听一个 重要 $$$i$$$ 课,那么您在接下来的 $$$k$$$ 课中无法入睡,也就是说,您还必须在 $$$i+1、i+2、\ldots、i+k$$$ 课中保持清醒(或者直到一天结束,如果剩余课数少于 $$$k$$$)。
对于不属于 重要,除非上述规则迫使您保持清醒,否则您可以在这些时间里睡觉。
您的任务是找出您今天可以睡完的最大课程数。
$$$^{\text{*}}$$$二进制字符串是每个字符为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$ 的字符串。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 100$$$)。
每个测试用例的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$ ($$$s_i = \mathtt 0$$$ 或 $$$\mathtt 1$$$)。
输出
对于每个测试用例,输出一个整数 - 您今天可以睡完的最大课程数。
示例
输入复制
44 110013 30003 10018 201000101
输出复制
1 3 2 2
注意
在第一个测试用例中,您必须听类 $$$1$$$ 和类 $$$4$$$。听完$$$1$$$课后,你就无法在$$$2$$$课上睡着了。所以你唯一可以睡觉的课程是 $$$3$$$ 课程。
在第二个测试用例中,您可以在所有课程中睡觉。
在第四个测试用例中,您只能在 $$$1$$$ 和 $$$5$$$ 课程中睡觉。