Table of Contents

# K – balanced string solution codechef starters 12

A binary string SS of length NN is called *KK-balanced string* if it holds the following property: For each index i(1≤i≤N)i(1≤i≤N) such that Si=Si= ‘1’, there must exist an index j(1≤j≤N)j(1≤j≤N) such that Sj=Sj= ‘1’ and ∣i−j∣=K∣i−j∣=K, where ∣x∣∣x∣ denotes the absolute value of xx.

For example, if K=1K=1, “00”, “110”, “011011” are 1-balanced strings, while “010” , “1001” are not; if K=2K=2, “10101”, “0101000101” are 2-balanced strings, while “0110” , “1001”, “010” are not.

Chef is given a binary string SS of length NN and an integer KK. He can perform the following operation on the string:

- Select an index of the string, and flip the character at that index. This means if the character was “0”, it becomes “1”, and vice versa.

What is the minimum number of operations Chef will have to perform so that the string becomes *KK-balanced*?

### Input Format

- The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains two space-separated integers N,KN,K.
- The second line of each test case contains a string SS.

### Output Format

For each test case, print a single line containing one integer – the minimum number operation Chef needs to perform on the given string to make it KK-balanced.

### Constraints

- 1≤T≤1051≤T≤105
- 2≤N≤1052≤N≤105
- 1≤K≤N1≤K≤N
- SS contains only characters ‘00‘ and ‘11‘.
- The sum of NN over all test cases does not exceed 106106.

### Sample Input 1

```
4
2 1
01
3 1
111
4 2
1101
5 3
11110
```

### Sample Output 1

```
1
0
1
2
```

### Explanation

**Test case 11**: Chef applies one operation on the index 22 and the string becomes “00” which is a 1-balanced string.

**Test case 22**: The given string is already 1-balanced.

**Test case 33**: Chef applies one operation on the index 33 and the string becomes “1111” which is a 2-balanced string.

**Test case 44**: Chef applies one operation on the index 22 and another operation on the index 33. Hence, the string becomes “10010” which is a 3-balanced stri