Cities

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

There are $n$ cities in Byteland, and the $i_{th}$ city has a value $a_i$. 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\leq10^5$), representing the number of test cases.
For each test case, the first line is an integer $n$($n\leq10^5$), representing the number of cities, the second line are n positive integers $a_i$($a_i\leq10^5$), representing their values.

Output

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

Sample Input

2
4
1 2 3 4
1
1

Sample Output

12
0

Hint

Source

“浪潮杯”山东省第九届ACM大学生程序设计竞赛(感谢山东财经大学)