카드 게임

근우와 명우가 카드 게임을 한다. $N$장의 카드가 일렬로 놓여 있고, 각 카드에는 수가 하나씩 적혀 있다. 근우가 먼저 시작해서 두 사람이 번갈아 턴을 진행한다. 한 턴에는 줄의 가장 왼쪽 카드나 가장 오른쪽 카드를 가져갈 수 있다. 카드가 하나도 남지 않을 때까지 턴을 반복한다. 각자의 점수는 자신이 가져간 카드에 적힌 수의 합이다.

두 사람 모두 자신의 점수를 가장 높이는 최선의 전략으로 게임에 임한다. 카드의 개수 $N$과 카드에 적힌 수가 주어질 때, 근우가 얻는 점수를 구하는 프로그램을 작성하시오.

예를 들어 카드가 왼쪽부터 4, 3, 1, 2 순서로 놓여 있다고 하자. 근우가 4를 가져가고 명우가 3을 가져간다. 이어서 근우가 2를 가져가고 명우가 마지막으로 1을 가져간다. 두 사람이 최선의 전략으로 임했을 때 근우의 점수는 6이다.

첫 줄에 테스트케이스의 수 $T$($1 \le T \le 50$)가 주어진다.

각 테스트케이스의 첫 줄에는 카드의 개수 $N$($1 \le N \le 1000$)이 주어진다. 둘째 줄에는 $N$개의 자연수가 공백으로 구분되어 주어지며, $i$번째 수는 왼쪽에서 $i$번째 카드에 적힌 수다. 카드에 적힌 수는 $1$ 이상 $10000$ 이하다.

각 테스트케이스마다 두 사람이 최선의 전략으로 임할 때 근우가 얻는 점수를 한 줄에 하나씩 출력한다.