D. 1D Ластик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть полоска бумаги $$$s$$$, которая имеет длину $$$n$$$ ячеек. Каждая ячейка может быть либо черной, либо белой. За одну операцию вы можете выбрать любые $$$k$$$ последовательных ячеек и сделать их все белыми.

Найдите минимальное количество операций, необходимых для удаления всех черных ячеек.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — длина полоски бумаги и целое число, используемое в операции.

Вторая строка каждого набора содержит строку $$$s$$$ длиной $$$n$$$, состоящую из символов $$$\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}$$$$$$