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
