#208도현이와 시우의 카드 게임

도현이와 시우는 재미있는 카드 게임을 한다. N개의 카드가 일렬로 놓여 있고, 각 카드에는 점수가 적혀 있다. 도현이부터 시작해 번갈아 가며 차례를 진행하는데, 한 차례에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 모두 없어질 때까지 차례는 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.

두 사람은 각자 자신의 점수를 최대로 만들기 위해 최선의 전략으로 게임에 임한다. 카드의 개수 N과 카드가 놓인 상태가 주어졌을 때 도현이가 얻는 점수를 구하는 프로그램을 작성하시오.

예를 들어 카드가 [4, 3, 1, 2]로 놓여 있다고 하자. 도현이는 먼저 4가 적힌 카드를 가져가고, 시우는 3이 적힌 카드를 가져간다. 이어서 도현이는 2가 적힌 카드를, 시우는 마지막으로 남은 1이 적힌 카드를 가져간다. 두 사람이 최선의 전략으로 임했을 때 도현이가 얻는 점수는 6이다.

입력의 첫 줄에는 테스트케이스의 수 T(1 ≤ T ≤ 50)가 주어진다.

각 테스트케이스마다 첫 줄에는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미한다. 카드에 적힌 수는 1 이상 10,000 이하이다.

각 테스트케이스마다 두 사람이 최선의 전략으로 임했을 때 도현이가 얻는 점수를 한 줄씩 출력한다.