HUST CLASS 14 160917

Vietnamese
Công ty Samsung đang xây dựng một hệ thống đập trữ nước dọc theo một con sông, để phân chia đập thành một số đoạn nhỏ hơn, công ty đã xây dựng các bức tường với chiều cao H để giữ nước bên trong đập và tránh áp suất nước quá cao lên thành đập.

Ví dụ dưới đây minh họa một đập nước với 3 block, các bức tường có chiều cao tương ứng là 2, 0 và 2.



Lượng nước tối đa có thể trữ trong đập nước này là 2 (vùng màu xanh).

Một ví dụ khác, đập nước dưới đây có thể trữ lượng nước tối đa là 3 + 3 + 1 + 3 = 10 đơn vị nước.





Cho trước trạng thái của một đập nước, hãy tính toán và in ra lượng nước tối đa mà đập nước có thể lưu trữ. Đáp án của 2 ví dụ trên lần lượt là 2 và 10.
Input
Tổng số lượng phép thử là T (1 <= T  <= 20) được cho trên dòng đầu tiên.

Mỗi phép thử được cho trên 2 dòng, dòng đầu tiên của mỗi phép thử là số lượng tường N (3 <= N <= 10000) của đập nước. Dòng tiếp theo mô tả chiều cao của các bức tường, là các số nguyên lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 100. Các giá trị trên cùng 1 dòng được ngăn cách bởi 1 dấu cách trắng.
Output
Hãy in đáp án của mỗi phép thử trên 1 dòng.
Sample




Input


Output




2
3
2 0 2
6
3 0 0 2 0 4


2
10







English
They are building a hydroelectric dams along a river, in some blocks of the dams, they built walls with height H to hold water into dams and prevent water pressure to these walls.


For example, the following dams have 3 blocks, the walls have height are 2, 0 and 2 corresponding.





The maximum water in which the dams can hold is 2 (the bule areas).


Another example, the following dams have maximum 3 + 3 + 1 + 3 = 10 water that it can hold.
 


Given the status of dams, print out the maximum water that it can hold. The answer for the two above example should be 2 and 10 corresponding.
Input
The total number of test cases T (1 <= T  <= 20) will be given the in the first line.
Each test case will be given in the following 2 lines, the first line of each test case is a number of blocks of the dams N (3 <= N <= 10000). The next line is numbers indicate the height of walls built on blocks of dams. The height in the same line are separated with a blank space. The height of walls are non negative integers number between 0 and 100 inclusive.
Output
Print the answer for each test case on 1 line.
Sample




Input


Output




2
3
2 0 2
6
3 0 0 2 0 4


2
10