Watchtowers

Let us travel back to a time when the finest means of transport was a steed, castles towered over cities, princesses were beautiful and knights were brave. In those very times lived our new hero, Captain Lucjusz.

Captain Lucjusz manages the watchtowers that keep one of the royal cities safe. There are $N$ watchtowers, arranged in a circle: the first watchtower is adjacent to the second and to the $N$-th, the second is adjacent to the first and the third, and so on.

In Captain Lucjusz's day there were no ministries yet, but bureaucracy already existed. At any moment the captain expects a visit from the royal inspectors who check compliance with norms and regulations. The officials will want to inspect some of the watchtowers under his command. The captain may pick any connected fragment of his network of watchtowers (that is, one made up of consecutively adjacent watchtowers) to be the subject of the inspection.

Captain Lucjusz has assigned to every watchtower an integer (negative, zero, or positive) describing the impression that, in his opinion, a visit to that watchtower will make on the inspectors. The score of the whole inspection is the sum of the impressions the inspectors gather in the watchtowers they visit. Compute the maximum score Captain Lucjusz can hope for.

The fragment chosen for inspection must contain at least one watchtower and, in the extreme case, may contain all of them.

The first line of input contains a natural number $Z$ ($1 \le Z \le 10$), the number of test sets. The test sets then follow one after another.

The first line of a test set contains a natural number $N$ ($1 \le N \le 1000000$), the number of watchtowers under Captain Lucjusz's command.

The second line of the set contains $N$ space-separated integers $w_i$ ($-1000 \le w_i \le 1000$), the impression each watchtower is expected to make on the inspectors.

For each test set, print on its own line the maximum inspection score that can be achieved.