Maximize Ones After a Flip

Given a binary string, you are allowed to perform exactly one flip operation on any non-empty contiguous substring. The flip operation converts every '0' to '1' and every '1' to '0'.

Formally, let ( s ) be the given binary string and ( ones(s) ) be the number of '1's in ( s ). For any substring ( s[i \ldots j] ), flipping it contributes a net change of ( \Delta = (#, 0's \ in\ s[i \ldots j]) - (#, 1's \ in\ s[i \ldots j]) ). The goal is to maximize ( ones(s) + \Delta ) over all choices of substrings (including the possibility of not increasing the count if no beneficial flip exists).

inputFormat

The first line contains an integer ( t ) denoting the number of test cases. Each test case consists of two inputs separated by space: an integer ( n ) representing the length of the binary string, and a binary string ( s ) of length ( n ). Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer in a new line representing the maximum number of '1's that can be obtained after performing exactly one flip operation. Output is written to standard output (stdout).## sample

3
3 110
5 01100
4 0000

3
4
4