该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

负责人

• 035966_L3

注意

本题的样例没有放在子任务 0 中，而是放在了其他地方：

其中样例 1 会被评测两次。

本题的子任务依赖关系如下：

本题需要使用文件读写（ricecake.in / ricecake.out）。

题目背景

这天晚上，Sleeping Goose 买了一串涂了辣椒酱的年糕。

题目描述

Sleeping Goose 所买到的年糕的竹签上有 $n$ 个位置可以串年糕，但有的位置串了年糕（年糕不能移动），有的位置则没有。

Sleeping Goose 希望按照某种顺序吃掉每一块年糕，但它希望尽量不蹭掉辣椒酱。具体来说，当它选择吃掉某一块年糕时，它的嘴会蹭到其他所有距离它不超过 $k$ 个位置的年糕。

Sleeping Goose 的嘴每蹭到某一块年糕一次，就会有 $1$ 单位辣椒酱被蹭下来。现在它想问你：在最优的吃法下，它一共会蹭掉多少单位辣椒酱？

输入格式

本题有多组数据。

第一行输入一个整数 $T$，表示测试数据的数量。

对于每组测试数据：

第一行两个整数 $n,k$。

第二行一个长度为 $n$ 的 01 串 $S$，描述 Sleeping Goose 所买到的年糕，其中 1 代表对应位置有年糕，0 代表对应位置没有年糕。

输出格式

对于每组数据，输出一行一个整数，表示 Sleeping Goose 在最优的吃法下一共会蹭掉多少单位辣椒酱。

样例

2
1 0
1
7 6
0000000

0
0

2
9 1
111010111
32 12
00110000100000000001000000110110

4
14

样例 2 解释

对于第一组数据，一种最优的吃法如下：

• 吃掉位置 $5$ 的年糕。
• 吃掉位置 $3$ 的年糕，蹭到位置 $2$ 的年糕。
• 吃掉位置 $2$ 的年糕，蹭到位置 $1$ 的年糕。
• 吃掉位置 $1$ 的年糕。
• 吃掉位置 $8$ 的年糕，蹭到位置 $7$ 和位置 $9$ 的两块年糕。
• 吃掉位置 $9$ 的年糕。
• 吃掉位置 $7$ 的年糕。

数据范围

对于 $100\%$ 的数据，$1 \le T \le 100$，$1 \le n \le 10^5$，$0 \le k \le n-1$。

本题共有四个等分的子任务，各子任务的特殊限制如下：

1. $n \le 6$。
2. $n \le 100$。
3. 保证 $k=n-1$。
4. 无特殊限制。