← 返回题目列表

Codeforces · 1873/D

D. 1D 橡皮擦

中文机器翻译题面 查看原题

给你一张 $$$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}$$$$$$