정말 이상한 수열

오랜 전통에 따라, 가장 좋은 문제 지문은 짧게 유지한 것이다.

정수 수열이 주어질 때, 길이가 홀수인 연속 부분수열의 합 중 최댓값을 구하시오.

첫째 줄에 테스트 케이스의 수 $z$가 주어진다. 이어서 각 테스트 케이스의 설명이 주어진다.

각 테스트 케이스의 첫째 줄에는 수열의 길이 $n$이 주어진다 ($1 \leq n \leq 1\,000\,000$).

다음 줄에는 수열의 원소 $n$개 $a\_1, a\_2, \ldots, a\_n$이 주어진다 ($-10^9 \leq a\_i \leq 10^9$).

모든 테스트 케이스에서 수열 길이의 합은 $5\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 최댓값을 한 줄에 하나씩 출력한다.