在單人操作的積木消除小遊戲後，小 T 和小 S 還準備了一項雙人互動的棋盤對弈小遊戲。

遊戲在一套特制的十週年紀念棋盤上進行。棋盤上面分佈著帶有分值的格子，參與的雙方需要輪流控制棋子向前跳躍，搶佔格子上的分數，以最大化自己和對手分數的差值。

這套特制的棋盤由 $n$ 個格子組成，其中格子 $i$ ($3 \le i \le n$) 的分值為正整數 $a_i$。

你決定與你的隊友進行一場對弈。遊戲開始時，你佔據了格子 1 並放上了自己的棋子，而你的隊友佔據了格子 2 並放上了他的棋子，且此時僅有這兩個格子被佔據。雙方的初始得分均為零。

遊戲由你率先行動，之後雙方輪流進行。在每次行動中，設當前行動玩家的棋子位於格子 $x$，則該玩家必須選擇一個步數 $d \in \{1, 2, 3, 4\}$，滿足 $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$。

對於第二組測試數據，一種可能的對局結果為 OXOXOXOX，得分差為 $0$。 對於第三組測試數據，一種可能的對局結果為 OX..OXOOOX，得分差為 $-7$。 對於第四組測試數據，一種可能的對局結果為 OX..OXXXO，得分差為 $8$。 對於第五組測試數據，一種可能的對局結果為 OXXXOXOO，得分差為 $90$。 對於第六組測試數據，一種可能的對局結果為 OX..OXO.XO，得分差為 $1000000000$。

輸入格式 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