题目描述

你有一条长度为 $n$ 的棋盘纸带。每个格子要么是白色，要么是黑色。

你需要将最少多少个白色格子重新染成黑色，才能在纸带上得到一段长度为 $k$ 的连续黑色格子？

如果输入数据中已经存在一段长度为 $k$ 的连续黑色格子，则输出 $0$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

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

每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2\cdot10^5$）。第二行是由字母 'W'（白色）和 'B'（黑色）组成的字符串，长度为 $n$。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出格式

对于每组测试用例，输出一个整数，表示至少需要将多少个白色格子染成黑色，才能得到一段长度为 $k$ 的连续黑色格子。

说明/提示

在第一个测试用例中，$s$="BBWBW"，$k=3$。只需将 $s_3$ 染黑，得到 $s$="BBBBW"。此时字符串中包含一段长度为 $k=3$ 的连续黑色格子。

在第二个测试用例中，$s$="BBWBW"，$k=5$。只需将 $s_3$ 和 $s_5$ 染黑，得到 $s$="BBBBB"。此时字符串中包含一段长度为 $k=5$ 的连续黑色格子。

在第三个测试用例中，$s$="BBWBW"，$k=1$。字符串 $s$ 已经包含一段长度为 $k=1$ 的连续黑色格子。

由 ChatGPT 4.1 翻译

样例

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

1
2
0
1