题目描述

你有一个机器人朋友，他们排成一排，从左至右的每列依次为 $1,2,\ldots,n$。初始时，有些机器人是关机的，而有些机器人是开机的。

你的手机能够控制这些机器人，但它并非总是那么灵活。具体地，有一个常数 $1 \leq a \leq n-1$，你仅能用你的手机做以下两种操作：

1. 选择连续的 $a$ 个机器人并将其全部设置为关机。
2. 选择连续的 $a+1$ 个机器人并将其全部设置为开机。

你希望找到，经过若干（可能为 $0$）次操作后，处于开机状态的机器人个数最大值。

输入格式

本题中有多组测试数据，第一行包含一个整数 $T$ ($1 \leq T \leq 4\cdot10^4$)，表示测试数据组数。每组测试数据的格式如下：

第一行，两个整数 $n$ 和 $a$ ($2 \leq n \leq 2\cdot10^5$, $1 \leq a \leq n-1$)。

接下来一行，一个长度为 $n$ 仅包含 0 和 1 的字符串 $s$。描述初始时机器人的状态。具体地，第 $i$ 个机器人初始处于开机状态，当且仅当 $s_i =$ 1。

保证所有测试数据中，$n$ 的总和不超过 $4\cdot10^5$。

输出格式

对于每组数据，输出仅一行一个整数，表示开机状态的机器人个数的最大值。

4
3 1
001
4 3
0101
5 2
10110
10 4
1011010001

3
2
5
5

解释 #1

1. 对于第一组数据，可以执行一次操作使得所有机器人开机：选择位置1和2的机器人（当前关机），将它们开机。
2. 对于第二组数据，无法进行任何有效操作，因此答案是初始开机数量2。