K개의 파일이 있고, 각 파일의 크기가 주어진다. 매번 임의의 두 파일을 골라 하나로 합칠 수 있으며(파일의 순서나 인접 여부와는 무관하게 어떤 두 파일이든 선택할 수 있다), 두 파일을 합치는 비용은 두 파일 크기의 합이다. 모든 파일을 하나로 합치는 데 필요한 총 비용의 최솟값을 출력하라.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 파일의 개수 K (3 ≤ K ≤ 1,000,000)가 주어지고, 두 번째 줄에는 K개 파일의 크기가 공백으로 구분되어 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

각 테스트 케이스마다 모든 파일을 하나로 합치는 데 필요한 최소 비용을 한 줄에 출력한다.

예제 입력 1

2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 1

300
826