题目描述

给你一条长度为 $n$ 的纸带 $s$，每个格子要么是黑色，要么是白色。在一次操作中，你可以选择任意连续的 $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$。

输出格式

对于每个测试用例，输出一个整数，表示将所有黑色格子变为白色所需的最少操作次数。

样例

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}$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1873D，英文题名 1D Eraser。