A14245 | Partial Replacement

You are given a number $k$ and a string $s$ of length $n$ , consisting of the characters '.' and '\*'. You want to replace some of the '\*' characters with 'x' characters so that the following conditions are met:

- The first character '\*' in the original string should be replaced with 'x';
- The last character '\*' in the original string should be replaced with 'x';
- The distance between two neighboring replaced characters 'x' must not exceed $k$ (more formally, if you replaced characters at positions $i$ and $j$ ( $i < j$ ) and at positions $[i+1, j-1]$ there is no "x" symbol, then $j-i$ must be no more than $k$ ).

For example, if $n=7$ , $s=$ .\*\*.\*\*\* and $k=3$ , then the following strings will satisfy the conditions above:

- .xx.\*xx;
- .x\*.x\*x;
- .xx.xxx.

But, for example, the following strings will not meet the conditions: - .\*\*.\*xx (the first character '\*' should be replaced with 'x');
- .x\*.xx\* (the last character '\*' should be replaced with 'x');
- .x\*.\*xx (the distance between characters at positions $2$ and $6$ is greater than $k=3$ ).

Given $n$ , $k$ , and $s$ , find the minimum number of '\*' characters that must be replaced with 'x' in order to meet the above conditions.

The first line contains one integer $t$ ( $1 \le t \le 500$ ). Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $k$ ( $1 \le k \le n \le 50$ ).

The second line of each test case contains a string $s$ of length $n$ , consisting of the characters '.' and '\*'.

It is guaranteed that there is at least one '\*' in the string $s$ .

It is guaranteed that the distance between any two neighboring '\*' characters does not exceed $k$ .

For each test case output the minimum number of '\*' characters that must be replaced with 'x' characters in order to satisfy the conditions above.