波利卡普和他的朋友想要参观一家新餐厅。餐厅的桌子沿直线排列。人们已经坐在一些桌子旁。这些表按照从左到右的顺序从 $$$1$$$ 到 $$$n$$$ 进行编号。餐厅的状态由长度为 $$$n$$$ 的字符串描述,其中包含字符“1”(桌子被占用)和“0”(桌子为空)。
餐厅规则禁止人们坐在 $$$k$$$ 或以下的距离。也就是说,如果一个人坐在第 $$$i$$$ 号桌,那么所有编号从 $$$i-k$$$ 到 $$$i+k$$$ 的桌子(第 $$$i$$$-th 除外)都应该是免费的。也就是说,任意两个占用表的数量的绝对差必须严格大于$$$k$$$。
例如,如果 $$$n=8$$$ 且 $$$k=2$$$,则:
- 字符串“10010001”、“10000010”、“00000000”、“00100000”满足餐厅的规则;
- 字符串“10100100”、“10011001”、“11111111”不满足餐厅的规则,因为它们每个都有一对距离小于或等于$$$k=2$$$的“1”。
具体地,如果餐厅的状态是由不带“1”的字符串或带有一个“1”的字符串来描述的,则满足餐厅的要求。
给您一个二进制字符串 $$$s$$$ 来描述餐厅的当前状态。保证字符串 $$$s$$$ 满足餐厅的规则。
找出您可以占用的最大空闲餐桌数量,以免违反餐厅规则。从形式上来说,最多可以用“1”替换多少个“0”才能仍然满足要求?
例如,如果 $$$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$$$) - 餐厅的桌子数量和两个人之间允许的最小距离。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,由“0”和“1”组成 - 餐厅中空闲和占用餐桌的描述。给定的字符串满足餐厅的规则 - 任何两个“1”的索引之间的差异大于 $$$k$$$。
一次测试中所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——您可以占用的桌子数量,以免违反餐厅的规则。如果无法获取额外的表,那么显然您需要输出$$$0$$$。
示例
输入 #1
6 6 1 100010 6 2 000000 5 1 10101 3 1 001 2 2 00 1 1 0
输出 #1
1 2 0 1 1 1
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,答案是 $$$2$$$,因为您可以选择第一个和第六个表。
在第三个测试用例中,如果不违反餐厅规则,则不能占用任何免费餐桌。