给定一个由 $$$n$$$ 数字组成的数组 $$$a$$$ 和一个数字 $$$k$$$。值 $$$a_i$$$ 描述了第 $$$i$$$ 天的天气:如果第 $$$i$$$ 天下雨,则 $$$a_i = 1$$$;否则,如果第 $$$i$$$ 天天气良好,则 $$$a_i = 0$$$。
吉恩想要参观尽可能多的山峰。一次徒步到达山顶需要 $$$k$$$ 天,并且在这些天中的每一天,天气都必须良好 ($$$a_i = 0$$$)。也就是说,正式而言,只有当所有 $$$j$$$ $$$(i \leq j \leq i + k - 1)$$$ 的所有 $$$a_j = 0$$$ 时,他才能在 $$$i$$$ 那天开始徒步旅行。
每次徒步结束后,在开始下一次徒步之前,Jean 必须至少休息一天,这意味着在徒步旅行后的第二天,他不能再进行另一次徒步旅行。
求 Jean 可以访问的最大山峰数量。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出一个整数:Jean 可以进行的最大徒步次数。
示例
输入复制
55 10 1 0 0 07 30 0 0 0 0 0 03 11 1 14 20 1 0 16 20 0 1 0 0 0
输出复制
3 2 0 0 2
注意
在第一个样本中:
- Day $$$1$$$ — 天气很好,Jean 去徒步旅行。 ($$$a_1 = 0$$$)
- Day $$$2$$$ — 强制休息。
- Day $$$3$$$ — 天气又好,Jean 进行了第二次徒步旅行。 ($$$a_3 = 0$$$)
- 天 $$$4$$$ — 休息。
- Day $$$5$$$ — 天气很好,第三次徒步旅行。 ($$$a_5 = 0$$$)
在第二个示例中:
- 从 $$$1$$$ 到 $$$3$$$ — 三天的好天气,Jean 去徒步旅行。 ($$$a_1 = a_2 = a_3 = 0$$$)
- Day $$$4$$$ — 强制休息。
- 从 $$$5$$$ 到 $$$7$$$ — 又是三天好天气,Jean 进行了第二次徒步旅行。 ($$$a_5 = a_6 = a_7 = 0$$$)
在第三个示例中:
- 没有好天气的日子($$$a_i = 1$$$ 对于所有 $$$i$$$)