CF2154A.Notelock

Teto is playing the hit rhythm game osu!. The game can be described by a binary string$^{\text{∗}}$ $s$ of length $n$ and a positive integer $k$ where the following will happen in order:

• You will choose some positions in $s$ to protect.
• Then for each $i$ ($1 \le i \le n$) in increasing order, Teto can set $s_i$ to $\mathtt{0}$ if all the following are true:
  • $s_i = \mathtt{1}$,
  • $s_i$ is not protected,
  • the previous $k - 1$ elements do not contain $\mathtt{1}$. More formally, $\mathtt{1}$ does not occur in $s_{\max(1, i - k + 1)},\ldots,s_{i - 1}$.

You dislike Teto (for some reason). So determine the minimum number of positions you need to protect to force her to leave $s$ unchanged.

$^{\text{∗}}$A binary string is a string that only consists of characters $\mathtt{0}$ and $\mathtt{1}$.

Teto 正在玩热门节奏游戏 osu！。该游戏可用一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$ 和一个正整数 $k$ 来描述，其规则如下（按顺序执行）：

• 你需选择 $s$ 中的若干位置进行保护；
• 接着，对每个 $i$（$1 \le i \le n$），按 $i$ 递增的顺序，若满足以下全部条件，则 Teto 可将 $s_i$ 设为 $\mathtt{0}$：
  • $s_i = \mathtt{1}$，
  • $s_i$ 未被保护，
  • 前 $k - 1$ 个元素中不包含 $\mathtt{1}$。更严格地，$\mathtt{1}$ 不出现在子串 $s_{\max(1, i - k + 1)},\ldots,s_{i - 1}$ 中。

你不喜欢 Teto（出于某种原因）。因此，请确定你需要保护的最少位置数，使得 Teto 无法对 $s$ 做任何修改（即强制 $s$ 保持不变）。

$^{\text{∗}}$二进制字符串是指仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each testcase contains integers $n$ and $k$ ($2 \le n \le 1000$; $2 \le k \le n$) — the length of $s$ and $k$.

The second line of each test case contains a binary string $s$ of length $n$ consisting of characters $\mathtt{0}$ and $\mathtt{1}$.

The sum of $n$ across all testcases does not exceed $1000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

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

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成。

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

For each testcase, output the minimum number of positions you need to protect to force Teto to leave the string unchanged.

对于每个测试用例，输出你需要保护的最少位置数，以迫使 Teto 保持字符串不变。

For the first testcase, you can protect the first element and have: $s = \mathtt{\color{red}{1}1}$. Now Teto cannot change $s_1$ because it is protected and cannot change $s_2$ because $s_1 = \mathtt{1}$. It can be proven this is optimal.

For the second testcase, you can protect only the first element and have $s = \color{red}{\mathtt{1}}\mathtt{00001}$. Teto cannot change $s_1$ because it is protected and she cannot change $s_6$ because there is $\mathtt{1}$ in the previous $k - 1$ elements ($\color{blue}{\mathtt{10000}}\mathtt{1}$).

For the fourth testcase, you must protect $s_1,s_3,s_5,s_7$ and have $s = \mathtt{\color{red}{1}0\color{red}{1}0\color{red}{1}0\color{red}{1}}$. It can be shown that this is optimal. For example, if you did not protect $s_3$, then Teto can change it to $\mathtt{0}$ ($\mathtt{\color{red}{1}\color{blue}{0}10\color{red}{1}0\color{red}{1}}$)

对于第一个测试用例，你可以保护第一个元素，得到：$s = \mathtt{\color{red}{1}1}$。此时 Teto 无法修改 $s_1$（因其已被保护），也无法修改 $s_2$（因为 $s_1 = \mathtt{1}$）。可以证明该方案是最优的。

对于第二个测试用例，你只需保护第一个元素，得到 $s = \color{red}{\mathtt{1}}\mathtt{00001}$。Teto 无法修改 $s_1$（因其已被保护），也无法修改 $s_6$（因为在前 $k - 1$ 个元素中存在 $\mathtt{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 可将其改为 $\mathtt{0}$（$\mathtt{\color{red}{1}\color{blue}{0}10\color{red}{1}0\color{red}{1}}$）。