F. Maximum Trust
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After seeing the problem set for the 2024 Spring TeamsCode contest, Chessbot has no trust. This is not ideal so to gain more trust he goes to $$$N$$$ different testers which each have a certain value $$$a_i$$$ (which may be negative). As Chessbot goes through the testers he keeps a "trust score" which is initially $$$0$$$. Every time he goes to a tester, he can either add or multiply that tester's value to his trust score. What is the maximum amount of trust Chessbot can achieve if he goes through all the testers in order from $$$1$$$ to $$$N$$$.

* Note that it is possible for Chessbot to have negative trust.

Input

The first line contains the integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) denoting the number of test cases.

The first line of every test case contains the integer $$$N$$$ ($$$1 \leq N \leq 100$$$) where $$$N$$$ is the amount of testers Chessbot goes to.

The next line of each test case contains $$$N$$$ space separated integers $$$a_1, a_2, \cdots, a_N$$$ ($$$-1000 \leq a_i \leq 1000)$$$ denoting the value of each tester.

Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.

Testcases $$$1-5$$$: All $$$a_i$$$ are non-negative.

Testcases $$$6-20$$$: No additional constraints.

Output

For each case, a single integer describing the maximum trust Chessbot can achieve.

Note that the answer is guaranteed to fit in a 64 bit integer.

Example
Input
4
4
4 0 1 2
3
3 -2 -2
4
-2 -4 -2 -8
3
2 -10 4
Output
10
12
128
4
Note

For the first test case, it is optimal to add the first $$$3$$$ values, then multiply for the fourth one.

In the second test case, to get the maximum you add the first value, then multiply for the next two values.

For the third test case, add the first value and multiply the next three.

For the fourth and final test case, multiply the first two values then add the third.

 —

Problem Idea: Bossologist

Problem Preparation: Bossologist

Occurrences: Novice 5