Trong trò chơi StarCraft II, Hiệp sĩ Thánh đường cấp cao (High Templar) là đơn vị AOE quan trọng của tộc Protoss, phát huy vai trò to lớn ở giai đoạn giữa và cuối trận đấu. Kỹ năng "Bão linh năng" của nó có thể tiêu hao lượng lớn linh năng để gây sát thương hủy diệt lên quân địch trong một vùng, thường được dùng để đối phó với các đơn vị máu thấp như bộ binh sinh học của Terran hay Hydralisk, Mutalisk của Zerg.

Bạn điều khiển $n$ Hiệp sĩ Thánh đường cấp cao, để thuận tiện ta đánh số họ là $1,2, \cdots,n$. Mỗi Hiệp sĩ Thánh đường cấp cao cần một lượng linh năng nhất định để chiến đấu, mỗi người có một giá trị linh năng $a_i$ biểu thị lượng linh năng họ sở hữu ($a_i$ không âm nghĩa là Hiệp sĩ này đang thừa $a_i$ điểm linh năng so với trạng thái tốt nhất, $a_i$ âm nghĩa là Hiệp sĩ này còn cần thêm $-a_i$ điểm linh năng nữa mới đạt trạng thái chiến đấu tốt nhất). Bây giờ hệ thống ban cho các Hiệp sĩ của bạn một khả năng: truyền linh năng. Mỗi lần bạn có thể chọn một $i \in[2,n-1]$, nếu $a_i \ge 0$ thì hai Hiệp sĩ hai bên, tức là hai Hiệp sĩ $i-1$ và $i+1$, sẽ rút từ Hiệp sĩ $i$ mỗi người $a_i$ điểm linh năng; nếu $a_i<0$ thì hai Hiệp sĩ hai bên, tức là hai Hiệp sĩ $i-1,i+1$, sẽ đưa cho Hiệp sĩ $i$ mỗi người $-a_i$ điểm linh năng. Diễn đạt một cách hình thức là $(a_{i-1},a_i,a_{i+1})\leftarrow (a_{i-1}+a_i,-a_i,a_{i+1}+a_i)$.

Linh năng là công cụ tác chiến rất hiệu quả, nhưng đồng thời cũng rất nguy hiểm và không ổn định. Một Hiệp sĩ Thánh đường cấp cao sở hữu quá nhiều hay quá ít linh năng đều không tốt. Định nghĩa độ bất ổn của một nhóm Hiệp sĩ Thánh đường cấp cao là $\max\limits_{i=1}^n{|a_i|}$. Hãy dùng số lần thao tác truyền linh năng không giới hạn để làm cho độ bất ổn của nhóm Hiệp sĩ Thánh đường cấp cao mà bạn điều khiển là nhỏ nhất.

Dữ liệu vào

Bài này gồm nhiều nhóm truy vấn. Dòng đầu tiên của đầu vào chứa một số nguyên dương $T$ là số nhóm truy vấn.

Tiếp theo lần lượt là dữ liệu của từng nhóm truy vấn.

Dòng đầu tiên của mỗi nhóm truy vấn chứa một số nguyên dương $n$, là số lượng Hiệp sĩ Thánh đường cấp cao.

Dòng tiếp theo chứa $n$ số $a_1,a_2, \cdots,a_n$.

Dữ liệu ra

In ra $T$ dòng. Mỗi dòng một số nguyên, lần lượt là đáp án của từng nhóm truy vấn.

Ví dụ 1

Input

3 3
5 -2 3
4
0 0 0 0
3
1 2 3

Output

3
0
3

Ví dụ 2

Input

3 4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1

Output

5
7
4

Ghi chú

Giải thích ví dụ

Với nhóm truy vấn thứ nhất:

Sau khi thực hiện thao tác truyền lên Hiệp sĩ Thánh đường cấp cao số $2$ thì $a_1=3$, $a_2=2$, $a_3=1$. Đáp án là $3$.

Với nhóm truy vấn thứ hai:

Lượng linh năng mà nhóm Hiệp sĩ Thánh đường cấp cao này sở hữu vừa đúng để họ đạt trạng thái chiến đấu tốt nhất.

Phạm vi dữ liệu

Với tất cả các test, $T \le 3$, $3 \le n \le 3\times10^5$, $|a_i| \le 10^9$.

Khi chấm sẽ dùng $25$ test để kiểm tra chương trình của bạn, giới hạn của mỗi test như sau:

Nguồn: Lanqiao Cup 2019 vòng tỉnh bảng B, bài J.