У вас есть полоска клетчатой бумаги длины \(n\). Каждая клетка либо белая, либо чёрная.
Сколько минимум клеток надо перекрасить из белого цвета в чёрный, чтобы на полоске существовал отрезок из \(k\) последовательных клеток чёрного цвета?
Если входные данные таковы, что отрезок \(k\) чёрных последовательных клеток уже существует, то выведите 0.
Выходные данные
Для каждого из \(t\) наборов входных данных выведите целое число — минимальное количество клеток, которые надо перекрасить из белого в чёрный цвет, чтобы существовал отрезок из \(k\) подряд идущих чёрных клеток.
Примечание
В первом наборе входных данных примера \(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'.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
|
1
2
0
1
|