카드 게임

$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]$가 된다.