在單人操作的積木消除小遊戲後，小 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