题目描述

Teto 正在玩热门音游 osu!。这个游戏可以用一个二进制字符串 $s$（长度为 $n$）和一个正整数 $k$ 来描述，其中会依次发生以下事情：

• 你可以选择字符串 $s$ 中的一些位置进行保护。
• 然后对于每一个 $i$（$1 \le i \le n$），Teto 按顺序可以将 $s_i$ 变为 $0$，如果满足以下所有条件：
  • $s_i = 1$；
  • $s_i$ 没有被保护；
  • 前 $k-1$ 个元素中没有 $1$。更形式化地说，$s_{\max(1, i-k+1)},\ldots,s_{i-1}$ 中没有出现 $1$。

你不喜欢 Teto（出于某些原因）。所以你想要让她无法改变 $s$，即 $s$ 保持不变，请问你最少需要保护多少个位置？

$^*$ 一个二进制字符串仅包含字符 $0$ 和 $1$。

输入格式

输入包含多组测试用例。第一行为测试用例个数 $t$（$1 \le t \le 100$）。接下来每组测试用例如下：

每组测试的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 1000$；$2 \le k \le n$），分别表示字符串的长度和 $k$ 的值。

每组测试的第二行为一个长度为 $n$ 的二进制字符串 $s$，仅包含字符 $0$ 和 $1$。

所有测试用例中 $n$ 的总和不超过 $1000$。

输出格式

每组测试用例，输出一个整数，表示你需要保护的最少位置数，才能使 Teto 无法改变字符串。

说明/提示

对于第一个测试用例，你可以保护第一个元素，此时 $s = \mathtt{\color{red}{1}1}$。Teto 无法改变 $s_1$，因为它已被保护，同时也无法改变 $s_2$，因为 $s_1 = 1$。可以证明这是最优方案。

对于第二个测试用例，你只需要保护第一个元素，此时 $s = \color{red}{\mathtt{1}}\mathtt{00001}$。Teto 无法改变 $s_1$，因为它被保护；也无法改变 $s_6$，因为在前 $k-1$ 个元素中存在 $1$（$\color{blue}{\mathtt{10000}}\mathtt{1}$）。

对于第四个测试用例，你需要保护 $s_1,s_3,s_5,s_7$，此时 $s = \mathtt{\color{red}{1}0\color{red}{1}0\color{red}{1}0\color{red}{1}}$。可以证明这是最优解。例如，如果你没有保护 $s_3$，那么 Teto 可以将其改为 $0$（$\mathtt{\color{red}{1}\color{blue}{0}10\color{red}{1}0\color{red}{1}}$）。

由 ChatGPT 5 翻译

样例

9
2 2
11
6 6
100001
5 3
10000
7 2
1010101
7 4
0000001
3 3
010
3 2
011
7 4
1001001
8 3
00000000

1
1
1
4
1
1
1
1
0