Circleland

You are visiting Circleland, and you finally walk into the famous art exhibition you have wanted to see for a long time. The exhibition has $N$ rooms arranged in a cycle, and every room holds some artistic pieces. The rooms are named $R_1, R_2, \dots, R_N$. There are also $N$ corridors, named $C_1, C_2, \dots, C_N$, of lengths $L_1, L_2, \dots, L_N$ respectively. Corridor $C_i$ connects rooms $R_i$ and $R_{i+1}$, and $C_N$ connects rooms $R_N$ and $R_1$. The whole exhibition therefore forms a cycle. You can walk in both directions in every corridor.

There is a single entrance in room $R_1$, and there is an exit in every room. Nothing in the corridors is worth seeing, so you want to walk as little as possible inside them. Compute the minimum total distance you have to walk in corridors if you enter through the entrance, visit all rooms, and leave through any exit.

The first line contains one integer $T$, the number of test cases. ($1 \le T \le 100$)

Each of the next $T$ lines contains one test case. A case starts with an integer $N$, the number of rooms in the exhibition ($2 \le N \le 100\,000$), followed by $N$ numbers, the lengths of the corridors $L_1, L_2, \dots, L_N$ in this order. ($1 \le L_i \le 1\,000\,000$)

The sum of the lengths of all corridors does not exceed $1\,000\,000\,000$.

For each test case, print on a single line the minimum total distance you have to walk in corridors to visit all rooms.