C. Flipping Cells
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ cells in a row, represented by a binary string $$$s$$$ of length $$$n$$$: 0 denotes white and 1 denotes black.

In one operation, you may toggle the color of one cell. You may perform at most $$$b$$$ operations. A black segment is a maximal nonempty contiguous segment of black cells. Find the minimum possible number of black segments after the operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10000$$$). Description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$b$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le b \le n$$$).

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

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one line containing the answer.

Print one integer: the minimum possible number of black segments.

Example
Input
4
9 2
111010111
7 0
1010101
5 3
00100
12 2
011010001101
Output
1
4
0
2
Note

In the first test case, changing cells $$$4$$$ and $$$6$$$ to black produces 111111111, which has one black segment.

In the second test case, no operation is allowed, so the four original black segments remain.

In the third test case, changing the only black cell to white removes all black segments.

In the fourth test case, changing cells $$$4$$$ and $$$11$$$ to black leaves two black segments, achieving the optimum $$$2$$$.