파일 합치기 3

소설가 김대전은 소설을 여러 장(chapter)으로 나누어 쓰고, 각 장을 서로 다른 파일에 저장한다. 모든 장을 다 쓰면 파일을 합쳐 완성본 하나로 만든다. 합치는 방법은 언제나 파일 두 개를 골라 하나로 만드는 것이고, 이렇게 만든 임시 파일도 다른 파일과 다시 합칠 수 있다. 이 과정을 반복해 마지막에는 파일 하나만 남긴다.

파일 두 개를 합치는 비용은 두 파일 크기의 합이다. 각 장이 담긴 파일의 크기가 주어질 때, 파일을 모두 하나로 합치는 데 드는 비용의 최소 합을 구한다.

예를 들어 네 장을 담은 파일 C1, C2, C3, C4의 크기가 각각 40, 30, 30, 50이라고 하자. C2와 C3을 합쳐 임시 파일 X1을 만들면 비용 60이 든다. 이어서 C1과 X1을 합쳐 X2를 만들면 비용 100이 들고, 마지막으로 X2와 C4를 합치면 비용 150이 든다. 비용의 합은 60 + 100 + 150 = 310이다. 합치는 순서를 바꾸면 비용이 줄어든다. C1과 C2를 합쳐 Y1을, C3과 C4를 합쳐 Y2를 만든 뒤 Y1과 Y2를 합치면 비용의 합은 70 + 80 + 150 = 300이다.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 데이터의 개수 $T$가 주어진다. 각 테스트 데이터는 두 줄이다. 첫 줄에는 소설을 구성하는 장의 수를 나타내는 양의 정수 $K$ ($3 \le K \le 1{,}000{,}000$)가 주어진다. 둘째 줄에는 1장부터 $K$장까지 각 장이 담긴 파일의 크기를 나타내는 양의 정수 $K$개가 공백으로 구분되어 주어진다. 파일 크기는 $10{,}000$을 넘지 않는다.

표준 출력에 출력한다. 테스트 데이터마다 정확히 한 줄에, 모든 장을 파일 하나로 합치는 데 필요한 최소 비용을 출력한다.