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