[Hidden]

#### Description

There are n cities in Byteland, and the ith city has a value ai. The cost of building a bidirectional road between two cities is the sum of their values. Please calculate the minimum cost of connecting these cities, which means any two cities can reach each other.

#### Input

The first line is an integer T(T≤10^5), representing the number of test cases.
For each test case, the first line is an integer n(n≤10^5), representing the number of cities, the second line are n positive integers ai(ai≤10^5), representing their values.

#### Output

For each test case, output an integer ans, the minimum cost of connecting these cities.

#### Samples

Input Copy
2
4
1 2 3 4
1
1

Output
12
0


#### Source

##### Problem Information

 Time Limit: 1000MS (C/C++,Others×2) Memory Limit: 128MB (C/C++,Others×2) Special Judge: No AC/Submit: 1 / 2 Tags:
##### Contests involved

 1017. 2018 SD ACM