Little IR12660 visited a school in Vaslui. He went to talk with the principal of the school to get his insight into education. The principal told him that there is only one thing important in the Vasluian culture: the social endurance. And the only purpose of the school is to instill this endurance into the students. However, school is too short to actually help all students, so the principal is happy if the school managed something close enough. More formally:
You are given a binary string $$$s$$$ of length $$$n$$$. In one operation, you can flip a character (change $$$0$$$ to $$$1$$$ or $$$1$$$ to $$$0$$$).
Your task is to determine the minimum number of operations needed to ensure that, for any contiguous subarray of length greater than or equal to $$$k$$$, the character $$$1$$$ is the majority element (it appears at least as many times as $$$0$$$ does).
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
Each test case consists of:
- A single line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — the length of the binary string and the minimum length of subarrays to consider.
- The second line contains a binary string $$$s$$$ of length $$$n$$$.
It is guaranteed that the total length of all strings $$$s$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the minimum number of operations required.
55 20001012 41101111011104 100005 3110009 2110101010
2 0 4 2 2
In the first testcase, to ensure that $$$1$$$ is the majority in all subarrays of length $$$\geq 2$$$, you can perform $$$2$$$ flips:
- Flip the second character to get $$$01010$$$.
- Flip the third character to get $$$01110$$$.
In the second testcase, no flips are required because $$$1$$$ is already the majority for all subarrays of length $$$\geq 4$$$.
