Problem Statement:

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 R_{1}, R_{2}, ..., R_{N}. There are also N corridors, named C_{1}, C_{2}, ..., C_{N}, of lengths L_{1}, L_{2}, ..., L_{N}, respectively. Each corridor C_{i} connects the two rooms R_{i} and R_{i+1}, except C_{N} which connects R_{N} and R_{1}. 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 R_{1}, 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 Format:

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, L_{1}, L_{2}, ..., L_{N}, in this order (1 ≤ L_{i} ≤ 1000,000).

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

Output Format:

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.

Sample Input:

2
5 1 1 1 1 1
7 100 15 20 42 33 15 24

Sample Output:

4
149