题目描述

你被给定一条长度为 $n$ 的纸条 $s$。每个单元格都是黑色或白色。在一个操作中，你可以选择任意 $k$ 个连续的单元格，并将它们都变成白色。

找到将所有单元格都变为白色的最小操作次数。

输入格式

第一行包含一个整数 $t(1≤t≤1000)$ — 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k(1≤k≤n≤2×10^5)$ — 纸的长度和操作中使用的整数。

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

所有测试用例中 $n$ 的总和不超过 $2×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

样例说明

在第一个测试用例中，你可以执行以下操作： WBWWWB→WWWWWB→WWWWWW

在第二个测试用例中，你可以执行以下操作： WWBWBWW→WWWWWWW

在第三个测试用例中，你可以执行以下操作： BWBWB→BWWWW→WWWWW