Bộ bàn cờ đặc biệt này bao gồm $n$ ô, trong đó ô $i$ ($3 \le i \le n$) có giá trị là số nguyên dương $a_k$.

Bạn quyết định chơi một ván cờ với đồng đội của mình. Khi bắt đầu trò chơi, bạn chiếm ô 1 và đặt quân cờ của mình vào đó, trong khi đồng đội của bạn chiếm ô 2 và đặt quân cờ của họ vào đó. Tại thời điểm này, chỉ có hai ô này bị chiếm. Điểm số ban đầu của cả hai bên đều bằng 0.

Bạn là người đi trước, sau đó hai bên luân phiên thực hiện lượt đi. Trong mỗi lượt, giả sử quân cờ của người chơi hiện tại đang ở ô $x$, người chơi đó phải chọn một bước nhảy $d \in \{1, 2, 3, 4\}$ thỏa mãn $x + d \le n$ và ô $x + d$ chưa bị chiếm. Sau đó, người chơi cộng giá trị của ô tương ứng $a_{x+d}$ vào điểm số của mình và di chuyển quân cờ đến ô $x + d$. Sau khi nhảy xong, người chơi đó sẽ chiếm giữ ô mới này vĩnh viễn. Đặc biệt, nếu không tồn tại bất kỳ bước nhảy hợp lệ nào, người chơi đó sẽ không thể thực hiện hành động trong lượt này và bỏ qua lượt. Trò chơi kết thúc khi cả hai bên đều không thể thực hiện hành động.

Rõ ràng, cả bạn và đồng đội đều là những người chơi cờ giỏi và đủ thông minh, luôn áp dụng chiến thuật tối ưu trong suốt ván đấu. Để dự đoán trước kết quả, bạn cần tính toán giá trị tổng điểm của bạn trừ đi tổng điểm của đồng đội khi trò chơi kết thúc.

Dữ liệu vào

Mỗi bộ dữ liệu chứa nhiều trường hợp kiểm thử. Dòng đầu tiên chứa một số nguyên dương $T$ ($1 \le T \le 10^3$), biểu thị số lượng trường hợp kiểm thử. Đối với mỗi trường hợp kiểm thử:

• Dòng đầu tiên chứa một số nguyên dương $n$ ($6 \le n \le 10^5$), biểu thị số lượng ô trên bàn cờ.
• Dòng thứ hai chứa $n - 2$ số nguyên dương $a_3, a_4, \dots, a_n$ ($1 \le a_k \le 10^9$), lần lượt biểu thị giá trị của mỗi ô.

Đảm bảo tổng $n$ trên tất cả các trường hợp kiểm thử không vượt quá $10^5$.

Dữ liệu ra

Đối với mỗi trường hợp kiểm thử, in ra một dòng chứa một số nguyên duy nhất, biểu thị giá trị tổng điểm của bạn trừ đi tổng điểm của đồng đội.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

5
0
-7
8
90
1000000000

Ghi chú

Dưới đây, một chuỗi có độ dài $n$ được sử dụng để biểu thị kết quả ván đấu, trong đó ký tự . biểu thị ô đó chưa bị ai chiếm, ký tự O biểu thị ô đó bị bạn chiếm, và ký tự X biểu thị ô đó bị đồng đội của bạn chiếm.

Đối với trường hợp kiểm thử đầu tiên, trong lượt đi đầu tiên, bạn có ba lựa chọn sau: Chọn bước nhảy $d = 2$, nhảy đến ô 3, kết quả ván đấu là OXOXXO, chênh lệch điểm là $-6$; Chọn bước nhảy $d = 3$, nhảy đến ô 4, kết quả ván đấu là OX.OOX, chênh lệch điểm là $5$; * Chọn bước nhảy $d = 4$, nhảy đến ô 5, kết quả ván đấu là OX..OX, chênh lệch điểm là $-1$.

Do đó, kết quả ván đấu là OX.OOX, chênh lệch điểm là $5$.

Đối với trường hợp kiểm thử thứ hai, một kết quả có thể xảy ra là OXOXOXOX, chênh lệch điểm là $0$.

Đối với trường hợp kiểm thử thứ ba, một kết quả có thể xảy ra là OX..OXOOOX, chênh lệch điểm là $-7$.

Đối với trường hợp kiểm thử thứ tư, một kết quả có thể xảy ra là OX..OXXXO, chênh lệch điểm là $8$.

Đối với trường hợp kiểm thử thứ năm, một kết quả có thể xảy ra là OXXXOXOO, chênh lệch điểm là $90$.

Đối với trường hợp kiểm thử thứ sáu, một kết quả có thể xảy ra là OX..OXO.XO, chênh lệch điểm là $1000000000$.

Dữ liệu vào 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

Dữ liệu ra 2

5
13
8
3
9
9