Partial Replacement

题意翻译

有一个由 `.` 和 `*` 组成的字符串，你需要将 `*` 修改成 `x` ，使得每两个没有其他 `x` 的 `x` 之间的距离小于等于 $k$。 特别地，第一个 `*` 和，最后一个 `*` 必须要改变。 求出当字符串满足条件时，最少需要改变的次数。 **本题有 $t$ 组测试数据** 第一行有一个变量 $t$ $(1\leq t \leq 500)$， 表示测试数据的数量。 对于每一组测试数据，第一行有两个变量 $n$ 和 $k$ $(1\leq k \leq n \leq 500)$。第二行有一个字符串，只包含 `.` 和 `*` 。 数据保证字符串中至少有一个`*`，且任意两个相邻的`*`字符之间的距离不超过 $k$ 。

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

3
1
3
2
1