Digo want to build a graph consisting of N nodes and N-1 edges. The graph must be connected. An edge is adjacent to the two nodes that it connects. The degree of a node in the graph is equal to the number of edges adjacent to the node.

You are given N scores. The score of a node with degree d is d-th score. The score of a graph is the sum of the scores of its nodes.

Your program should compute and print the maximum possible score for a graph you can construct.

Constraints:
N is between 1 and 50, inclusive.
Each scores will be between 0 and 10,000, inclusive.

Input:
First line contains 't', number of test cases.
Next t lines follow, First integer is 'N', followed by N scores.

Output:
't' lines, the answer to the question.

Sample Input:
3
3 1 3 0
4 0 0 0 10
3 5 0 0

Sample Output:
8
10
15

Explanation:
In first case, since N is 3, there are 4 nodes, one possible way can be n----n----n----n, it gives score: 1+3+3+1=8.