11001100 SUSTech Online Judge
Problem 1100 --get the max value

1100: get the max value

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 84  Solved: 27
[Submit][Status][Web Board]

Description

Now you have an array A with size N(1<=N<=300000, Ai > 0 and Ai < 1000000).  you can also chose two elements in A such that Ai = Aj and make them become one element with value Ai + Aj.  And you should print the maximum value you can get finally. The time you use the operation is unlimited which means you can do the operation when you find two elements such that Ai = Aj.

For example, if A = {3, 1, 2, 1}, you can chose (1, 1) and make them become their sum, then A = {2, 2, 3}, then you can choose (2, 2) and get a 4, so A = {3, 4}, the max element you can get is 4.


Input

The first line of the input is T, means the number of test cases;

For each test case, the first line is N, which is the size of A, and the second line contains N elements, the ith of them is Ai.

Output

For each test case, print the maximum value you can get in one line.

Sample Input

2
8
1 1 1 1 2 2 2 2
1
3

Sample Output

8
3

HINT


Huge input, use scanf in c++ and faster io method in java or other language.





Source

 

[Submit][Status]