카드 게임

$n$개의 카드가 덱에 쌓여 있다. 위에서 $i$번째 카드에는 정수 $a_i$가 적혀 있다. 카드에 적힌 정수는 변하지 않는다.

성호는 혼자 게임을 하려고 한다. 처음에 성호의 점수는 $0$이다. 매 턴마다 성호는 다음 중 하나의 행동을 할 수 있다.

• 현재 남아 있는 카드 개수보다 크지 않은 양의 홀수 $i$를 선택한다. 위에서 $i$번째 카드를 덱에서 제거하고, 그 카드에 적힌 수를 점수에 더한다.
• 현재 남아 있는 카드 개수보다 크지 않은 양의 짝수 $i$를 선택한다. 위에서 $i$번째 카드를 덱에서 제거한다.
• 게임을 종료한다. 게임을 끝내기 전에 모든 카드를 덱에서 제거하지 않아도 된다.

성호의 최종 점수의 최댓값을 구하라.

각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 $t$가 주어진다($1 \le t \le 10^{4}$). 다음 줄부터 각각의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 정수 $n$이 주어진다($1 \le n \le 2 \cdot 10^{5}$).

두 번째 줄에 공백으로 구분된 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다($-10^{9} \le a_i \le 10^{9}$).

모든 테스트 케이스에서 $n$의 총합은 $2 \cdot 10^{5}$를 넘지 않는다.

각 테스트 케이스마다 정답을 한 줄에 출력한다.

첫 번째 테스트 케이스에서 성호는 다음 방법으로 $5$점을 얻을 수 있다.

1. 첫 번째 턴에서 $i=2$를 선택한다. 점수는 $0$점으로 유지되고, 위에서부터 남은 카드는 $[-4, -3, 5]$이다.
2. 두 번째 턴에서 $i=3$을 선택한다. 점수는 $5$점이 되고, 위에서부터 남은 카드는 $[-4, -3]$이다.
3. 세 번째 턴에서 게임을 종료한다. 최종 점수는 $5$점이다.

두 번째 테스트 케이스에서 성호는 다음 방법으로 $4$점을 얻을 수 있다.

1. 첫 번째 턴에서 $i=3$을 선택한다. 점수는 $3$점이 되고, 위에서부터 남은 카드는 $[1, -2, -4]$이다.
2. 두 번째 턴에서 $i=1$을 선택한다. 점수는 $4$점이 되고, 위에서부터 남은 카드는 $[-2, -4]$이다.
3. 세 번째 턴에서 게임을 종료한다. 최종 점수는 $4$점이다.

세 번째 테스트 케이스에서 성호는 다음 방법으로 $2$점을 얻을 수 있다.

1. 첫 번째 턴에서 $i=1$을 선택한다. 점수는 $-1$점이 되고, 위에서부터 남은 카드는 $[3, -5]$이다.
2. 두 번째 턴에서 $i=1$을 선택한다. 점수는 $2$점이 되고, 위에서부터 남은 카드는 $[-5]$이다.