题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个数字 $k$。数组 $a$ 的第 $i$ 天的值 $a_i$ 描述了当天的天气：如果第 $i$ 天下雨，则 $a_i = 1$；否则，如果天气晴朗，则 $a_i = 0$。

Jean 想要尽可能多地登顶。每次登顶需要恰好 $k$ 天，并且在这 $k$ 天内，每一天的天气都必须是晴朗的（即 $a_i = 0$）。也就是说，Jean 只能在第 $i$ 天开始登顶，当且仅当对于所有 $j$ 满足 $i \leq j \leq i + k - 1$，都有 $a_j = 0$。

每次登顶后，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 最多能登顶多少次。

说明/提示

在第一个样例中：

• 第 $1$ 天——天气晴朗，Jean 登顶一次（$a_1 = 0$）。
• 第 $2$ 天——强制休息。
• 第 $3$ 天——再次天气晴朗，Jean 登顶第二次（$a_3 = 0$）。
• 第 $4$ 天——休息。
• 第 $5$ 天——天气晴朗，第三次登顶（$a_5 = 0$）。

因此，Jean 最多可以登顶 $3$ 次，每次登顶之间都要休息一天。

在第二个样例中：

• 第 $1$ 天到第 $3$ 天——连续三天晴朗，Jean 登顶一次（$a_1 = a_2 = a_3 = 0$）。
• 第 $4$ 天——强制休息。
• 第 $5$ 天到第 $7$ 天——又是连续三天晴朗，Jean 登顶第二次（$a_5 = a_6 = a_7 = 0$）。

总共 Jean 可以登顶 $2$ 次。

在第三个样例中：

• 没有一天是晴朗的（所有 $a_i = 1$）。

Jean 无法登顶，答案为 $0$。

由 ChatGPT 4.1 翻译

样例

5
5 1
0 1 0 0 0
7 3
0 0 0 0 0 0 0
3 1
1 1 1
4 2
0 1 0 1
6 2
0 0 1 0 0 0

3
2
0
0
2