Maximum Ones After a Single Flip

You are given a binary string of length ( n ). You are required to perform exactly one flip operation on a contiguous substring of the binary string. In a flip operation, every character in the chosen substring is inverted: i.e., (0) becomes (1) and (1) becomes (0) (formally, (0 \rightarrow 1) and (1 \rightarrow 0)).

Your task is to determine the maximum number of (1)'s obtainable after performing exactly one flip. Note that if the string consists entirely of (1)'s, any flip will reduce the number of (1)'s, so you should choose the best (least damaging) flip.

A hint to solve this problem is to use Kadane's algorithm. Replace every (0) in the string with (+1) and every (1) with (-1) then find the maximum subarray sum. If the string contains all (1)'s, return ( n - 1 ).

inputFormat

The input begins with a single integer ( t ) representing the number of test cases. Each test case consists of two inputs on the same line: an integer ( n ) representing the length of the binary string and a binary string ( s ) of length ( n ).

Example input: 5 5 11111 8 00000000 6 110100 1 0 1 1

outputFormat

For each test case, output a single integer representing the maximum number of (1)'s that can be obtained after exactly one flip operation. Each result should be printed on a new line.## sample

5
5 11111
8 00000000
6 110100
1 0
1 1

4
8
5
1
0