この特製の棋盤は $n$ 個のマスで構成されており、そのうちマス $i$ ($3 \le i \le n$) の値は正の整数 $a_i$ です。

あなたとチームメイトで対局を行います。ゲーム開始時、あなたはマス 1 を占有して自分の駒を置き、チームメイトはマス 2 を占有して彼の駒を置きます。この時点で占有されているのはこの 2 つのマスのみです。両者の初期スコアはともに 0 です。

ゲームはあなたが先攻で、その後は両者が交互に行動します。各行動において、現在行動するプレイヤーの駒がマス $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$) が含まれ、データセットの数を示します。各データセットについて：

• 1 行目に正の整数 $n$ ($6 \le n \le 10^5$) が含まれ、棋盤のマス数を示します。
• 2 行目に $n - 2$ 個の正の整数 $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$) が含まれ、各マスの値を示します。

すべてのテストデータにおける $n$ の総和は $10^5$ を超えないことが保証されます。

出力

各テストデータについて、1 行に整数を 1 つ出力してください。これは、ゲーム終了時の「あなたの合計スコア」から「チームメイトの合計スコア」を引いた値です。

入出力例

入力 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 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