题目描述

星星：希望与治愈，太阳：成功与喜悦，月亮：迷茫与转变

这三张牌连在一起，也像是人生的一个过程：从迷茫中找到希望，最终迎来光明

给你一条长度为 $n$ 的序列 $s$，代表 $n$ 个星球的白天跟黑夜，每个星球要么是黑夜，要么是白天

现在你是奶龙，你可以选择任意连续的 $k$ 个星球，并将它们状态全部变为白天

请你求出将所有星球的黑夜变为白天所需的最少操作次数

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 2 \cdot 10^5$）
分别表示星球的个数 $s$ 和每次操作涉及的星球个数。
每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $\texttt{B}$（表示黑夜）和 $\texttt{W}$（表示白天）组成。
所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示将所有星球的黑夜变为白天所需的最少操作次数

样例

8
6 3
WBWWWB
7 3
WWBWBWW
5 4
BWBWB
5 5
BBBBB
8 2
BWBWBBBB
10 2
WBBWBBWBBW
4 1
BBBB
3 2
WWW

2
1
2
1
4
3
4
0

在第一个测试用例中，你可以进行如下操作：${\color{red}{\texttt{WBW}}}{\texttt{WWB}} \to \texttt{WWW}{\color{red}{\texttt{WWB}}} \to \texttt{WWWWWW}$。

在第二个测试用例中，你可以进行如下操作：$\texttt{WW}{\color{red}{\texttt{BWB}}}\texttt{WW} \to \texttt{WWWWWWW}$。

在第三个测试用例中，你可以进行如下操作：$\texttt{B}{\color{red}{\texttt{WBWB}}} \to {\color{red}{\texttt{BWWW}}}\texttt{W} \to \texttt{WWWWW}$。