파일 합치기

소설가 김대전은 소설을 여러 장으로 나누어 쓰고, 각 장을 서로 다른 파일에 저장한다. 모든 장을 다 쓰고 나면 파일을 합쳐 완성본 하나를 만든다. 합치는 방법은 이렇다. 파일 두 개를 합쳐 임시 파일 하나를 만들고, 임시 파일이나 원래 파일을 다시 두 개씩 합쳐 나간다. 합치는 두 파일은 장 번호가 서로 이어져 있어야 하고, 마지막에는 파일이 하나만 남는다. 파일 두 개를 합치는 비용은 두 파일 크기의 합이다.

예를 들어 이어진 네 장을 담은 파일 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 500$)가 주어진다. 둘째 줄에는 1장부터 $K$장까지의 파일 크기를 나타내는 양의 정수 $K$개가 공백으로 구분되어 주어진다. 파일 크기는 10,000을 넘지 않는다.

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