题目描述

给你一个数字k和一个长度为n的字符串s，由字符$.$和$*$组成。你想用$*$字符替换一些$*$字符，这样就能满足以下条件。

原始字符串中的第一个字符$*$应该被替换成$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≤t≤500）。然后是t个测试用例。

每个测试用例的第一行包含两个整数n和k（1≤k≤n≤50）。

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

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

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

输出格式

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

样例

input

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

output

3
1
3
2

数据范围与提示

（$1\le t\le 500$），（$1\le k\le n\le 50$）