Flip Flop Sum

Description:

Input:

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 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$$$.

Output:

For each test case, print the maximum possible sum of the array $$$a$$$ you can get in a separate line.

Sample Input:

4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1

Sample Output:

3
3
-2
4

Note:

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$$$.