У вас есть полоска бумаги \(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\).
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для удаления всех черных ячеек.
В первом наборе входных данных примера вы можете выполнить следующие операции: \(\)\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}\(\)
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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач