题目描述

给定一个数字 $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'，才能满足上述条件。

说明/提示

由 ChatGPT 4.1 翻译

样例

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

3
1
3
2
1