← 返回题目列表

Codeforces · 1506/B

B. 部分更换

中文机器翻译题面 查看原题

给你一个数字 $$$k$$$ 和一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 '.' 组成。和 '*'。您想要将一些“*”字符替换为“x”字符,以便满足以下条件:

- 原始字符串中的第一个字符“*”应替换为“x”;
- 原始字符串中的最后一个字符“*”应替换为“x”;
- 两个相邻替换字符“x”之间的距离不得超过 $$$k$$$(更正式地说,如果您在位置 $$$i$$$ 和 $$$j$$$ ($$$i < j$$$) 处替换了字符,并且在位置 $$$[i+1, j-1]$$$ 处没有“x”符号,则 $$$j-i$$$ 不得超过$$$k$$$)。

例如,如果 $$$n=7$$$、$$$s=$$$.**.*** 且 $$$k=3$$$,则以下字符串将满足上述条件:

- .xx.*xx;
- .x*.x*x;
- .xx.xxx。

- .**.*xx(第一个字符“*”应替换为“x”);
- .x*.xx*(最后一个字符“*”应替换为“x”);
- .x*.*xx(位置 $$$2$$$ 和 $$$6$$$ 处的字符之间的距离大于 $$$k=3$$$)。

给定 $$$n$$$、$$$k$$$ 和 $$$s$$$,找到必须用 'x' 替换的 '*' 字符的最小数量,以满足上述条件。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 50$$$)。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由字符“.”组成。和 '*'。

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

保证任意两个相邻'*'字符之间的距离不超过$$$k$$$。

输出

对于每个测试用例,输出必须替换为“x”字符的最小数量的“*”字符,以满足上述条件。

示例

输入 #1

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

输出 #1

3
1
3
2
1