题目描述

Teto 在玩节奏游戏 osu!。游戏可以用一个二进制字符串 $s$（长度为 $n$）和正整数 $k$ 描述，按如下顺序发生：

• $1$. 你选择在 $s$ 中若干位置进行保护。

• $2$. 然后按 $i$ 从 $1$ 到 $n$ 的顺序处理：若同时满足下列三条，则 Teto 可以把 $s_i$ 设为 $0$（即将该位从 1 变为 0）：

  • $s_i=1$；
  • 位置 $i$ 未被保护；
  • 前 $k-1$ 个元素中不包含 1，即在区间 $[s_{max(1,i-k+1)},s_{i-1}]$ 中不存在 1。

你不喜欢 Teto（某种原因），希望她不能将字符串 $s$ 进行任何改变（即在上述过程中字符串保持不变）。问：你至少需要保护多少个位置才能保证 Teto 无法改变 $s$ ？

注：二进制字符串仅由字符 0 和 1 构成。

输入格式

输入共有若干测试用例。

• 第一行包含一个整数 $t$，表示测试用例个数。
• 接下来描述 $t$ 个测试用例，每个测试用例包含两行：
  • 第一行包含两个整数 $n$ 和 $k$，表示字符串长度和参数 $k$。
  • 第二行包含一个长度为 $n$ 的二进制字符串 $s$。

输出格式

对于每个测试用例，输出一行，包含一个整数 —— 为了保证 Teto 不能修改字符串 $s$ 所需保护位置的最小数量。

样例输入

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

说明

样例解释

• 样例 $1$：可以保护第 $1$ 位，此时 $s=11$。$s_1$ 被保护不能变，$s_2$ 虽未被保护但因为 $s_1=1$，也不能被改为 $0$。最少需保护 $1$ 位。
• 样例 $4$：字符串 $s=1010101$，必须保护下标 $1,3,5,7$（共 $4$ 位），才能阻止 Teto 将任意未保护的 1 变为 0。

数据范围

• $1\le t\le 100$；
• 对每个测试用例，$2\le n\le 1000,\ 2\le k\le n$；
• 所有测试用例中 $\sum n \le 1000$。