You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Alice有一条长度为$n$的纸条$s$，每个格子是白色或黑色。她有一块橡皮擦，可以进行如下操作：选择任意连续的$k$个格子并将它们擦除成白色。

请你找到擦除所有黑色格子所需的最少操作次数。

输入格式

第一行包含一个整数$t$，表示测试用例的数量。

每个测试用例的第一行包含两个整数$n$和$k$，表示纸条的长度和连续擦除的格子数。

每个测试用例的第二行包含一个长度为$n$的字符串$s$，包含字符$B$（表示黑色格子）或$W$（表示白色格子）。

输出格式

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

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

提示

【样例解释】

第一个测试用例可以进行如下操作：

$WBWWWB→WWWWWB→WWWWWW$

第二个测试用例可以进行如下操作：

$WWBWBWW→WWWWWWW$

第三个测试用例可以进行如下操作：

$BWBWB→BWWWW→WWWWW$

【数据范围】

对于100%数据，$1\leq t \leq 1000,1\leq k \leq n \leq 2\cdot 10^5$。所有测试用例中$n$的总和不超过$2\cdot10^5$。