Equator

Interview

Time limit1sMemory limit256 MB

Summary

Each test case gives city profits around a circle and asks for the most profitable contiguous block, or zero when all are losses.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Cities lie on a circular equator. The gang may land once, travel in one direction, and rob a contiguous block of cities. Each city has a profit or loss. Find the maximum total profit, or 0 if they should not land at all.

Input

The first line contains $T$ . Each test case gives $n$ and $n$ integers $c_i$ .

Output

For each test case, print the maximum total profit.

Examples1

Example 1

Input

3
3 1 2 3
8 4 5 -1 -1 1 -1 -1 5
2 -1 -1

Expected output

6
14
0