Minimum Operations to Make Binary String All Ones

You are given a binary string s and an integer k. In one operation, you can invert (flip) all bits in any substring of length k. Inversion means changing '0' to '1' and '1' to '0'. Your task is to determine the minimum number of operations required to transform the string s so that every character becomes '1'.

Using a greedy strategy, you iterate over the string from left to right. Whenever you encounter a '0', you flip the next k characters (which may convert some '1's to '0's, but this approach guarantees a minimal covering of zeros by non-overlapping intervals).

Formally, you want to cover all positions where the bit is 0 with the minimum number of intervals of length k. The number of required operations can be expressed as: $$\text{operations} = \min{ \text{number of intervals of length } k \text{ that cover all zeros in } s }.$$

inputFormat

The first line of the input contains a single integer t representing the number of test cases. Each of the following t lines describes a test case with two parameters: an integer k and a binary string s, separated by a space.

outputFormat

For each test case, print a single integer on a new line: the minimum number of operations required to transform the binary string s into a string of all '1's.## sample

3
3 010101
2 1100
4 0000

2
1
1