시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 0 0 0 0.000%

문제

Due to the development of online shopping, the logistics industry which is highly connected with goods shipping has been so prosperous that the great amount of employees is needed. Therefore, Alex, a truck driver in this growing industry, was supposed to transport several parcels scattering in the warehouse to other cities in his daily routine.

According to the official safety requirements to the trucks running in the highway, Alex had to tie up all the packages tightly so that he could settle the goods safely on his truck. Alex knew that the length of the cords needed for bundling the packages on the truck was based on the size of the packages themselves. Also, n packages can be tied up well after n − 1 bundles. Moreover, when bundling goods, Alex could only bundle two packages at one time to avoid scattering. Since the daily consumption of the cord was great and Alex was supposed to pay for it, he hopes to bundle all the goods with the shortest cord.

For example, there are 4 parcels in the size of 8, 5, 14, and 26 respectively. If Alex binds the first two together, the needed rope will be in the length of 13 (8+5 = 13) while the needed rope for the latter two packages will be 40 (14 + 26 = 40). If Alex keeps bundling these two items, the rope length he needs will be 53 (13 + 40 = 53). So the total length of the 4 packages will be 106 (13 + 40 + 53 = 106). If Alex tries another way by bundling the first two (8 + 5 = 13), adding up the third one (13 + 14 = 27), and then bundling the last item (27 + 14 = 53), he will only need the cord in the length of 93 (13 + 27 + 53 = 93). Now your mission is to help Alex finding the minimum length of the needed cord.

입력

The first line contains an integer T indicating the number of test cases. Each test case contains two lines. The first one contains a positive integer n indicating the number of packages. The second one contains n positive integers separated by a space to indicate the size of each parcel.

출력

For each test case, output the minimum length of the bundle rope required to tie all parcels together in one line.

제한

  •  1 ≤ T ≤ 10
  • 1 ≤ n ≤ 1000
  • The size of each parcel is at most 1000.

예제 입력 1

4
6
2 3 4 4 5 7
5
5 15 40 30 10
10
3 1 5 4 8 2 6 1 1 2
9
3 2 1 6 5 2 6 4 3

예제 출력 1

63
205
100
98