Chef has to work on a project for the next N hours. He is given a work plan to do this, which is given to you as a binary string S of length N. S_{i} = 1 if Chef has to work on the project during the i-th hour, and S_{i} = 0 if Chef is free during the i-th hour.

Chef would like to use some of his free time to take naps. He needs a minimum of K consecutive hours of free time to take a nap. What is the maximum number of naps that Chef can take during the next N hours?

Note that it is allowed for one nap to immediately follow another, i.e, Chef can wake up from one nap and then immediately take another one (if he has enough free time to do so), and these will be counted as different naps.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers N and K respectively.
• The second line of each test case contains a binary string S of length N denoting Chef's work plan.

------ Output Format ------

• For each test case, print a single line containing one integer — the maximum number of naps that Chef can take.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
- Sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$
$S$ is a binary string, i.e, each character of $S$ is either 0 or 1.

----- Sample Input 1 ------
3
4 1
1010
4 2
0100
11 3
00100000001
----- Sample Output 1 ------
2
1
2
----- explanation 1 ------
Test Case 1: Chef can take two naps starting from the $2^{nd}$ and $4^{th}$ hours respectively.

Test Case 2: Chef can take a nap starting from the $3^{rd}$ hour.

Test Case 3: Chef can take one nap starting from the $5^{th}$ hour and another starting from the $8^{th}$ hour.

见题面

见题面