치즈 게임

앨리스와 밥은 매년 열리는 Two-player Games and Applied Cryptography Symposium에 참가한 뒤, 좋아하는 게임을 하며 쉬려고 한다.

두 사람은 치즈 조각 $n$개를 한 줄로 놓고 1번부터 $n$번까지 번호를 붙였다. 치즈는 대체로 맛있지만 조각마다 맛의 정도가 다르다. $i$번째 조각의 맛의 정도는 $o_i$이다.

앨리스가 먼저 시작하고, 두 플레이어는 번갈아 가며 한 번씩 움직인다. 한 번의 움직임에서 플레이어는 판에 남아 있는 치즈 조각들 중 원하는 집합을 먹을 수 있다. 단, 그 집합에는 서로 이웃한 두 조각(즉, 임의의 $1 \le i \le n-1$에 대해 번호가 $i$와 $i+1$인 조각)이 함께 들어 있으면 안 된다. 조각의 번호는 바뀌지 않으므로 게임 도중에 새로운 이웃 쌍이 생기지 않는다.

두 플레이어 모두 자신이 먹은 조각의 맛의 정도 합을 최대화하려고 한다. 둘 다 최적으로 플레이할 때, 앨리스가 얻을 수 있는 합의 최댓값은 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 $z$가 주어진다 ($1 \le z \le 20$). 각 테스트 케이스는 다음 형식으로 주어진다.

테스트 케이스의 첫 줄에는 치즈 조각의 수 $n$이 주어진다 ($1 \le n \le 100\,000$). 둘째 줄에는 $n$개의 정수 $o_1, o_2, \ldots, o_n$ ($1 \le o_i \le 1\,000\,000$)이 주어지며, 각각 해당 조각의 맛의 정도다.

각 테스트 케이스마다 두 플레이어가 최적으로 플레이할 때 앨리스가 먹은 조각들의 맛의 정도 합을 정수 하나로 출력한다.