Вам заданы число \(k\) и строка \(s\) длины \(n\), состоящая из символов '.' и '*'. Вы хотите заменить некоторые из символов '*' на символы 'x', чтобы были выполнены следующее условия:
- Самый первый символ '*' в исходной строке должен быть заменен на 'x';
- Самый последний символ '*' в исходной строке должен быть заменен на 'x';
- Расстояние между двумя соседними замененными символами 'x' не должно превосходить \(k\) (более формально, если вы заменили символы на позициях \(i\) и \(j\) (\(i < j\)) и на позициях \([i+1, j-1]\) нет символа 'x', то \(j-i\) должно быть не больше \(k\)).
Например, если \(n=7\), \(s=\).**.*** и \(k=3\), то вы следующие строки будут удовлетворять условиям выше:
- .xx.*xx;
- .x*.x*x;
- .xx.xxx.
Но, например, следующие строки удовлетворять условиям не будут:
- .**.*xx (самый первый символ '*' должен быть заменен на 'x');
- .x*.xx* (самый последний символ '*' должен быть заменен на 'x');
- .x*.*xx (расстояние между символами на позициях \(2\) и \(6\) больше \(k=3\)).
Для заданных \(n\), \(k\) и \(s\) найдите минимальное количество символов '*', которые необходимо заменить на символы 'x', чтобы были выполнены условия выше.
Выходные данные
Для каждого набора входных данных выведите минимальное количество символов '*', которые необходимо заменить на символы 'x', чтобы были выполнены условия выше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*
|
3
1
3
2
1
|