You are visiting circleland, and you have long waited to visit their famous art exhibition. The exhibition has N rooms arranged in a cycle. In every room, there are some artistic pieces. The rooms are named R1 , R2 , ..., RN . There are also N corridors, named C1 , C2 , ..., CN , of lengths L1 , L2 , ..., LN , respectively. Each corridor Ci connects the two rooms Ri and Ri+1 , except CN which connects RN and R1 . Thus, the whole exhibition forms a cycle. You can walk in both directions in every corridor. 

There is a single entrance to the exhibition in room R1 , but there are exits in every room. As there is nothing interesting to see in the corridors, you would like to spend the least effort walking through corridors in the exhibition. Compute the minimum total distance you need to walk in corridors such that you enter from the entrance, exit from any exit and visit all rooms.

 Input

Your program will be tested on one or more test cases. The first line of the input will be a single integer T , the number of test cases (1 ≤ T ≤ 100). Next T lines contain the test cases, each on a single line. 

Each case starts with an integer N , the number of rooms in the exhibition (2 ≤ N ≤ 100, 000), followed by N numbers, the lengths of the corridors, L1 , L2 , ..., LN , in this order (1 ≤ Li ≤ 1,000,000).

The sum of the lengths of all corridors will not exceed 1,000,000,000.

Output

For each test case, output, on a single line, a single number representing the minimum total distance you have to walk in corridors such that you visit all rooms.

Example

Input:
2
5 1 1 1 1 1
7 100 15 20 42 33 15 24
Output:
4
149