题目描述

给定一个长度为 $n$ 的方格纸条，每个小方格可能是白色或黑色。

请问，将多少个白色小方格重新涂为黑色，可以使其上连续出现 $k$ 个黑色小方格？如果输入的方格纸条上本来已经有长度为 $k$ 的连续黑色区间，则输出 0。

输入格式

第一行包含一个整数 $t(1≤t≤10^4)$——测试用例的数量。

接下来，是 $t$ 个测试用例的描述。

输入的第一行包含两个整数 $n$ 和 $k(1≤k≤n≤2⋅10^5)$。第二行由字母 W（白色）和 B（黑色）组成，行长度为 $n$。

保证 $n$ 的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，请输出一个整数——需要重新涂黑的最小单元格数量，以便在条纹上有一个 $k$ 个连续黑色单元格的段。

测试样例

4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W

1
2
0
1

样例说明

在第一个示例中，$s=BBWBW，k=3$。只需要重新涂色 $s_3$ 即可得到 $s=BBBBW$。该字符串包含一个长度为 $k=3$ 的由字母 B 组成的连续段。

在第二个示例中，$s=BBWBW，k=5$。只需要重新涂色 $s_3$ 和 $s_5$ 即可得到 $s=BBBBB$。该字符串包含一个长度为 $k=5$ 的由字母 B 组成的连续段。

在第三个示例中，$s=BBWBW，k=1$。字符串 $s$ 已经包含一个长度为 $k=1$ 的由字母 B 组成的连续段。