Useless Trick
Description
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.
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$.
For each test case, print a single integer — the minimum number of operations.
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.
3
7 5 4
0011101
7 7 6
0100010
16 4 2
1111101010000000
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.