1506_B. Partial Replacement_34895
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.

Input

The first line contains one integer t (1 ≤ t ≤ 500). Then t test cases follow.

The first line of each test case contains two integers n and k (1 ≤ k ≤ n ≤ 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.

Output

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

Example

Input


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


Output


3
1
3
2
1
from __future__ import division
from sys import stdin, stdout
from collections import *

rstr = lambda: stdin.readline().strip()
rstrs = lambda: [str(x) for x in stdin.readline().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda: int(stdin.readline())
rints = lambda: [int(x) for x in stdin.readline().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
pr = lambda args, sep: stdout.write(sep.join(map(str, args)) + '\n')
ceil1, out = lambda a, b: (a + b - 1) // b, []

for _ in range(int(input())):
    n, k = rints()
    s = rstr()
    if s.count('*') == 1:
        print(1)
    else:
        be, en, ans = s.find('*'), s.rfind('*'), 1
        while be != en:
            new = min(be + k, n - 1)
            for j in range(new, be, -1):
                if s[j] == '*':
                    ans += 1
                    be = j
                    break
        print(ans)
