이 특수 제작된 보드는 $n$개의 칸으로 구성되어 있으며, 칸 $i$ ($3 \le i \le n$)의 점수는 양의 정수 $a_i$입니다.

당신은 팀원과 함께 대국을 하기로 했습니다. 게임이 시작될 때, 당신은 칸 1을 차지하고 자신의 말을 놓았고, 팀원은 칸 2를 차지하고 자신의 말을 놓았으며, 이때는 이 두 칸만 점유된 상태입니다. 양측의 초기 점수는 모두 0입니다.

게임은 당신이 먼저 시작하며, 이후 양측이 번갈아 가며 진행합니다. 매 차례마다 현재 행동하는 플레이어의 말이 칸 $x$에 위치해 있다면, 해당 플레이어는 $d \in \{1, 2, 3, 4\}$인 보폭 $d$를 선택해야 합니다. 이때 $x + d \le n$을 만족해야 하며, 칸 $x + d$는 아직 점유되지 않은 상태여야 합니다. 그 후 자신의 점수에 해당 칸의 점수 $a_{x+d}$를 더하고, 자신의 말을 칸 $x + d$로 이동시킵니다. 이동이 완료되면 해당 플레이어는 이 새로운 칸을 영구적으로 점유합니다. 특히, 어떠한 합법적인 이동 보폭도 존재하지 않는 경우, 해당 플레이어는 이번 턴에 행동할 수 없으며 차례를 넘깁니다. 양측 모두 행동할 수 없게 되면 게임이 종료됩니다.

게임 이론에 능숙한 당신과 팀원은 모두 충분히 똑똑하며, 대국에서 항상 최선의 전략을 취합니다. 대국 결과를 미리 추론하기 위해, 게임이 종료되었을 때 당신의 총 점수에서 팀원의 총 점수를 뺀 값을 계산해야 합니다.

입력

각 테스트 케이스에는 여러 개의 테스트 데이터가 포함되어 있습니다. 입력의 첫 번째 줄에는 데이터의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^3$)가 주어집니다. 각 테스트 데이터에 대하여:

• 첫 번째 줄에는 보드의 칸 수를 나타내는 정수 $n$ ($6 \le n \le 10^5$)이 주어집니다.
• 두 번째 줄에는 각 칸의 점수를 나타내는 $n - 2$개의 양의 정수 $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$)이 주어집니다.

모든 테스트 데이터에 대하여 $n$의 합은 $10^5$를 넘지 않습니다.

출력

각 테스트 데이터마다, 게임 종료 시 당신의 총 점수에서 팀원의 총 점수를 뺀 값을 한 줄에 하나씩 출력합니다.

예제

입력 1

6
6
1 6 3 4
10
1 1 1 1 1 1 1 1
10
1 1 1 1 1 1 1 10
9
1 1 1 1 1 1 10
8
10 1 1 1 1 100
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1

출력 1

5
0
-7
8
90
1000000000

참고

이하용 길이 $n$의 문자열로 대국 결과를 나타내며, 문자 .은 해당 칸이 점유되지 않음을, O는 당신이 점유함을, X는 팀원이 점유함을 의미합니다.

첫 번째 테스트 데이터에서, 첫 번째 행동 시 당신의 선택지는 다음과 같습니다: 보폭 $d=2$ 선택 시 칸 3으로 이동, 결과 OXOXXO, 점수 차 $-6$ 보폭 $d=3$ 선택 시 칸 4로 이동, 결과 OX.OOX, 점수 차 $5$ * 보폭 $d=4$ 선택 시 칸 5로 이동, 결과 OX..OX, 점수 차 $-1$

따라서 최선의 결과는 OX.OOX이며 점수 차는 $5$입니다.

입력 2

6
9
7 6 2 2 5 8 7
10
8 26 18 1 11 9 15 9
11
8 3 9 2 3 4 8 8 7
12
5 6 5 3 1 2 1 1 5 4
15
6 6 7 2 2 2 5 2 2 4 7 7 7
18
7 4 5 1 2 6 7 5 7 3 7 3 6 5 6 6

출력 2

5
13
8
3
9
9