CF1506B.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 \lt 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.

给你一个数字 $k$ 和一个长度为 $n$ 的字符串 $s$，其中只包含字符 . 和 *。你需要将字符串中部分 * 替换为 x，使得满足以下条件：

• 原字符串中第一个出现的 * 必须被替换为 x；
• 原字符串中最后一个出现的 * 必须被替换为 x；
• 任意两个相邻的被替换为 x 的字符之间的距离不能超过 $k$（更准确地说：若你在位置 $i$ 和 $j$（其中 $i \lt j$）处替换了 x，且在区间 $[i+1, j-1]$ 内没有其他 x，则必须满足 $j-i \le k$）。

例如，当 $n=7$、$s=$.**.***、$k=3$ 时，以下字符串满足上述条件：

• .xx.*xx；
• .x*.*x*x；
• .xx.xxx。

但以下字符串不满足条件：

• .*.*xx（第一个 * 未被替换为 x）；
• .x*.*xx*（最后一个 * 未被替换为 x）；
• .x*.*xx（位置 $2$ 与位置 $6$ 上的 x 之间的距离大于 $k=3$）。

给定 $n$、$k$ 和 $s$，求满足上述条件所需替换为 x 的 * 字符的最小数量。

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

第一行包含一个整数 $t$（$1 \le t \le 500$）。随后是 $t$ 组测试数据。

每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 50$）。

每组测试数据的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 '.' 和 '*' 组成。

保证字符串 $s$ 中至少有一个 '*'。

保证任意两个相邻的 '*' 字符之间的距离不超过 $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.

对于每个测试用例，输出为满足上述条件所需将 * 字符替换为 x 字符的最少个数。