파일 합치기 2

소설가 김대전은 소설을 여러 장(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 5000$)가 주어진다. 둘째 줄에는 1장부터 $K$장까지 각 장을 담은 파일의 크기가 순서대로 $K$개 주어진다. 파일의 크기는 10,000을 넘지 않는 양의 정수다.

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