You are given an array of n integers a_1, a_2, ldots, a_n . The integers are either 1 or -1 . You have to perform the following operation exactly once on the array a : What is the maximum possible value of a_1 + a_2 + ldots + a_n after applying the above operation? Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 500 ). Description of the test cases follows. The first line of each test case contains a single integer n ( 2 <= n <= 10^5 ), the length of the array a . The next line contains n integers a_1, a_2, ldots, a_n ( a_i = 1 or a_i = -1 ). The sum of n over all cases doesn't exceed 10^5 . For each test case, print the maximum possible sum of the array a you can get in a separate line. In the first case, we can choose index 4 and flip the signs of a_4 and a_5 . After this operation, the sum will be -1+1+1+1+1 = 3 . We can't make the sum larger than this. In the third case, the only option is to choose the index 1 .