Description

Problem B - Sticks

After inspecting the problem set TA give to HT, he feels a little tired and decides to go for a walk. As a naughty boy, HT picks up n sticks during his walk, each with a length a_i. HT wonders if he can choose three from the n sticks such that the three sticks can form a triangle with the maximum possible perimeter (周長). HT is a busy professor, so he wants you to help him decide the maximum possible perimeter of the triangles that could be formed.

Input

The first line contains an integer T, representing the number of testcases.

Each testcase contains two lines :

The first line contains an integer n, representing the number of sticks HT picks.

The second line contains n integer a_i, representing the length of each sticks.

It is guaranteed that :

• testcase #1 : Sample Input
• testcase #2~4 : T = 1, n = 3, 1 ≤ a_i ≤ 100
• testcase #5~8 : 1 ≤ T ≤ 10, 1 ≤ n ≤ 100, 1 ≤ a_i ≤ 100
• testcase #9~10 : 1 ≤ T ≤ 10, 1 ≤ n ≤ 1000, 1 ≤ a_i ≤ 100

If you can't pass testcase #9 & #10 immediately, try to solve another two problems first.  

Output

For each testcase, please output a line contains one integer represents the length of the triangle with the maximum possible perimeter. If the sticks can't form a triangle, please output -1.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss