Minimize Flips for 1-Burst Constraint

You are given an integer \( k \) and a binary string \( s \). Your task is to determine the minimum number of flips (changing a '1' to a '0') required so that every contiguous segment (or burst) of '1's in the string has a length of at most \( k \). A burst is defined as a maximal contiguous substring of '1's.

For example, if \( k = 1 \) and \( s = "1110101" \), the first burst consists of three consecutive '1's. To reduce this burst to a length of at most 1, you need to flip \( 3 - 1 = 2 \) bits. Hence, the answer is 2 for this test case.

Compute and print the required minimum number of flips for each test case.

inputFormat

The input begins with an integer \( T \) representing the number of test cases. Each of the next \( T \) lines contains a test case. Each test case consists of an integer \( k \) and a binary string \( s \) separated by a space.

outputFormat

For each test case, output a single integer representing the minimum number of flips required, each on a new line.

## sample

3
1 1110101
2 110011
0 1010101

2
0
4

</p>