AT_abc408_d [ABC408D] Flip to Gather

You are given a string $ S $ of length $ N $ consisting of `0` and `1`. You can perform the following operation any number of times (possibly zero): - Choose an integer $ i $ satisfying $ 1 \leq i \leq N $ , and change $ S_i $ from `0` to `1`, or from `1` to `0`. Your goal is to make the `1`s in $ S $ form **at most one** interval. Find the minimum number of operations required to achieve the goal. More precisely, the goal is to make $ S $ such that there exists a pair of integers $ (l,r) $ satisfying both of the following conditions. Find the minimum number of operations required to achieve the goal. - $ 1 \leq l \leq r \leq N+1 $ . - $ S_i= $ `1` and $ l \leq i < r $ are equivalent for each integer $ i $ satisfying $ 1 \leq i \leq N $ . It can be proved that the goal can always be achieved with a finite number of operations. $ T $ test cases are given, so solve each.

The input is given from Standard Input in the following format: > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ represents the $ i $ -th test case and is given in the following format: > $ N $ $ S $

Output $ T $ lines. The $ i $ -th line $ (1 \leq i \leq T) $ should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 In the first test case, if we perform the operation to change $ S_1 $ to `0`, the `1`s will form one interval. Also, the initial $ S $ does not satisfy the condition. Therefore, the answer is $ 1 $ . In the second test case, there are no `0`s in $ S $ , so no operations need to be performed. Therefore, the answer is $ 0 $ . In the third test case, there are no `1`s in $ S $ , so no operations need to be performed. Therefore, the answer is $ 0 $ . ### Constraints - $ 1 \leq T \leq 20000 $ - $ 1 \leq N \leq 2 \times 10^5 $ - $ S $ is a string of length $ N $ consisting of `0` and `1`. - For each input file, the sum of $ N $ over all test cases is at most $ 2 \times 10^5 $ . - $ T,N $ are integers.