本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1140. Cities


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
My history solutions

You didn't submit any solution!
Submit your solution

Login Register