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

Вам заданы число $$$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', чтобы были выполнены условия выше.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$). Далее следуют $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 50$$$).

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов '.' и '*'.

Гарантируется, что в строке $$$s$$$ есть хотя бы один символ '*'.

Гарантируется, что расстояние между любыми двумя соседними символами '*' не превосходит $$$k$$$.

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

Для каждого набора входных данных выведите минимальное количество символов '*', которые необходимо заменить на символы 'x', чтобы были выполнены условия выше.

Пример
Входные данные
5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*
Выходные данные
3
1
3
2
1