G. Useless Trick
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$. A binary string is called good if every substring of size $$$m$$$ has exactly $$$k$$$ number of $$$1$$$.

You can do this as many times operation as you like, in one operation you can choose an interval $$$[l,r]$$$ and flip it (turn $$$0$$$ into $$$1$$$, turn $$$1$$$ into $$$0$$$). You want to find the minimum number of operations to make the string good.

Input

Each test contains multiple test cases.

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

The first line of each test case contains three integer $$$n,m,k$$$ ($$$1\le k\le m\le n\le3000$$$).

The second line of each test case contains a single binary string $$$s$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Output

For each test case, print a single integer — the minimum number of operations.

Example
Input
3
7 5 4
0011101
7 7 6
0100010
16 4 2
1111101010000000
Output
1
2
4
Note

In the first case, we can choose interval $$$[2,2]$$$, then $$$s=0111101$$$, it's good.

In the second case, we can choose interval $$$[3,7]$$$ and $$$[6,6]$$$, then $$$s=0111111$$$, it's good.