서클랜드 전시관

서클랜드로 여행을 왔고, 오래전부터 보고 싶었던 유명한 미술 전시관에 들어간다. 전시관에는 방이 $N$개 있고 원형으로 이어져 있으며, 방마다 작품이 놓여 있다. 방의 이름은 $R_1, R_2, \dots, R_N$이다. 복도도 $N$개 있고, 이름은 $C_1, C_2, \dots, C_N$, 길이는 각각 $L_1, L_2, \dots, L_N$이다. 복도 $C_i$는 방 $R_i$와 방 $R_{i+1}$을 잇고, $C_N$은 방 $R_N$과 방 $R_1$을 잇는다. 그래서 전시관 전체가 하나의 원을 이룬다. 모든 복도는 양쪽 방향으로 지나갈 수 있다.

입구는 방 $R_1$에 하나만 있고, 출구는 모든 방에 있다. 복도에는 볼거리가 없으니 복도를 걷는 거리는 되도록 줄이고 싶다. 입구로 들어가서 모든 방을 방문한 뒤 아무 출구로나 나갈 때, 복도에서 걸어야 하는 최소 총 거리를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 전시관의 방 개수 $N$으로 시작하고 ($2 \le N \le 100\,000$), 이어서 복도의 길이 $L_1, L_2, \dots, L_N$이 이 순서대로 주어진다. ($1 \le L_i \le 1\,000\,000$)

복도 길이의 합은 $1\,000\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 모든 방을 방문하기 위해 복도에서 걸어야 하는 최소 총 거리를 한 줄에 출력한다.