给你一张 $$$s$$$ 的纸条,长度为 $$$n$$$ 个单元格。每个单元格要么是黑色的,要么是白色的。在操作中,您可以获取任何 $$$k$$$ 连续单元格并将它们全部设为白色。
找出删除所有黑色单元格所需的最少操作数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — 论文的长度和操作中使用的整数。
每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由字符$$$\texttt{B}$$$(代表黑色单元格)或$$$\texttt{W}$$$(代表白色单元格)组成。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 删除所有黑色单元格所需的最少操作数。
示例
输入 #1
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
输出 #1
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{WWWWWWWW}$$$$$$
在第三个测试用例中,您可以执行以下操作: $$$$$$\texttt{B}\color{red}{\texttt{WBWB}} \to \color{red}{\texttt{BWWW}}\texttt{W} \to \texttt{WWWWW}$$$$$$