Teto 正在玩热门节奏游戏 奥苏!。游戏可以用长度为 $$$n$$$ 的二进制字符串 $$$^{\text{*}}$$$ $$$s$$$ 和正整数 $$$k$$$ 来描述,其中将按顺序发生以下情况:
- 您将选择 $$$s$$$ 中的一些头寸进行保护。
- 然后,对于按升序排列的每个 $$$i$$$ ($$$1 \le i \le n$$$),如果满足以下所有条件,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(出于某种原因)。因此,请确定您需要保护的最少位置数,以迫使她保持 $$$s$$$ 不变。
$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出需要保护的最小位置数,以强制 Teto 保持字符串不变。
示例
输入复制
92 2116 61000015 3100007 210101017 400000013 30103 20117 410010018 300000000
输出复制
111411110
注意
对于第一个测试用例,您可以保护第一个元素并具有:$$$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}}$$$)