Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Partial Replacement

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

- .**.*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.

Input

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$$$.

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/23/2021 22:21:05 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|