Description

Alice have a friend Bob, they both smart,Today they are going to play a new game again

$a$. There are $N$ heap stones here

$b$. They took stones in turn

$c$. Only take stones from both ends, take a heap each time

$d$. Alice first

Format

Input

The first line is $T$, $T$ is TestCase$(0 < T <= 1000)$

The first line of each testcase is a number $N(0 < n <= 100)$

The next line each contain $N$ integers $x$ indicating the number of each heap.$(1 ≤ x ≤ 1000)$

Output

Case #TestCase: answer

Answer is the most stones Alice got

Samples

1
4
1 2 3 4

Case #1: 6