Mia is learning data structures, this semester. After her boyfriend, John, has given so many problems to her, this time, Mia gives John an interesting problem, or rather, an intellectual game.
In this problem, you are given an integer sequence a1, a2, ..., an (-1 ≤ ai ≤ 1, 1 ≤ i ≤ n). You are going to determine n - 1 operators op1, op2, ..., opn - 1 (opi is either '+' or '*', 1 ≤ i ≤ n - 1) so that the result of the expression S = a1 op1 a2 op2 a3 op3 ... opn - 2 an - 1 opn - 1 an is maximized.
Mia is only interested in the maximum result S, but John is unable to tell. Now, John has turned to you for help!
Explanations for the Sample Input and Output
For the first test case, there is only one integer, so we just need to output it: S = 1.
For the second test case, S = 1 + 1 + 1 + 0 = 3.
For the third test case, S = (-1) * (-1) + 0 = 1.
The first line is an integer T (1 ≤ T ≤ 120), indicates that there are T-group data.
For each test case, the first line contains one integer n (1 ≤ n ≤ 100,000).
The second line contains n integers a1, a2, ..., an (-1 ≤ ai ≤ 1, 1 ≤ i ≤ n).
There are no more than 10 test cases with n > 1,000.
For each test case, output one integer which is the maximum result S.