D. Черно-белая полоса
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Сколько минимум клеток надо перекрасить из белого цвета в чёрный, чтобы на полоске существовал отрезок из $$$k$$$ последовательных клеток чёрного цвета?

Если входные данные таковы, что отрезок $$$k$$$ чёрных последовательных клеток уже существует, то выведите 0.

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

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания $$$t$$$ наборов входных данных.

Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2\cdot10^5$$$). Вторая строка состоит из букв 'W' (белый цвет) и 'B' (чёрный цвет). Длина строки равна $$$n$$$.

Гарантируется, что сумма значений $$$n$$$ не превосходит $$$2\cdot10^5$$$.

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

Для каждого из $$$t$$$ наборов входных данных выведите целое число — минимальное количество клеток, которые надо перекрасить из белого в чёрный цвет, чтобы существовал отрезок из $$$k$$$ подряд идущих чёрных клеток.

Пример
Входные данные
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
Выходные данные
1
2
0
1
Примечание

В первом наборе входных данных примера $$$s$$$=«BBWBW» и $$$k=3$$$. Достаточно перекрасить $$$s_3$$$ и получить $$$s$$$=«BBBBW». В этой строке содержится отрезок длины $$$k=3$$$ из букв 'B'.

Во втором наборе входных данных примера $$$s$$$=«BBWBW» и $$$k=5$$$. Достаточно перекрасить $$$s_3$$$ и $$$s_5$$$ и получить $$$s$$$=«BBBBB». В этой строке содержится отрезок длины $$$k=5$$$ из букв 'B'.

Во третьем наборе входных данных примера $$$s$$$=«BBWBW» и $$$k=1$$$. В $$$s$$$ уже содержится отрезок длины $$$k=1$$$ из букв 'B'.