A. Simple Update - I
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string$$$^\dagger$$$ $$$s$$$ of length $$$n$$$ and an integer $$$k$$$.

You are allowed to do the following operation on $$$s$$$ :

  1. Choose any $$$i(k \le i \le n-k)$$$;
  2. Update all $$$s_{i},s_{i-1},s_{i-2},...,s_{i-k+2},s_{i-k+1}$$$ to $$$1$$$;
  3. Update all $$$s_{i+1},s_{i+2},s_{i+3},...,s_{i+k-1},s_{i+k}$$$ to $$$0$$$.

What are the maximum number of $$$1$$$'s in $$$s$$$ after performing the above operation infinitely many times (possibly zero)?

$$$^\dagger$$$ A binary string is a string which only contains $$$0$$$'s and $$$1$$$'s.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,k$$$ ($$$2 \le n \le 10^3$$$, $$$1 \le k \le ⌊\frac{n}{2}⌋$$$), the length of binary string and an integer.

The second line of each testcase contains a binary string $$$s$$$ of length $$$n$$$.

Output

For each test case, print a single integer — the maximum number of $$$1$$$'s in $$$s$$$ after performing the above operation infinitely many times(possibly zero).

Example
Input
6
2 1
00
2 1
01
3 1
101
3 1
111
4 2
1100
4 1
1010
Output
1
1
2
3
2
3
Note

In the $$$6$$$-th test case, $$$s = 1010$$$ and $$$k = 1$$$

Let choose $$$i = 2$$$, now $$$s_2$$$ becomes $$$1$$$ and $$$s_3$$$ becomes $$$0$$$. So $$$s = 1100$$$.

Let choose $$$i = 3$$$, now $$$s_3$$$ becomes $$$1$$$ and $$$s_4$$$ becomes $$$0$$$. So $$$s = 1110$$$.

Hence, maximum number of $$$1$$$'s in $$$s = 1110$$$ is $$$3$$$.