# Partial Replacement Solution Codeforces Round #710 Div. 3

You are given a number kk and a string ss of length nn, 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 kk (more formally, if you replaced characters at positions ii and jj (i<ji<j) and at positions [i+1,j−1][i+1,j−1] there is no “x” symbol, then j−ij−i must be no more than kk).

For example, if n=7n=7, s=s=.**.*** and k=3k=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 22 and 66 is greater than k=3k=3);

Given nn, kk, and ss, find the minimum number of ‘*’ characters that must be replaced with ‘x’ in order to meet the above conditions.Input

The first line contains one integer tt (1≤t≤5001≤t≤500). Then tt test cases follow.

The first line of each test case contains two integers nn and kk (1≤k≤n≤501≤k≤n≤50).

The second line of each test case contains a string ss of length nn, consisting of the characters ‘.’ and ‘*’.

It is guaranteed that there is at least one ‘*’ in the string ss.

It is guaranteed that the distance between any two neighboring ‘*’ characters does not exceed kk.Output

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

Example

Input

```5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*
```

Output

```3
1
3
2
1```

Solution : coming soon