IITKWPCD - Partition the sticks

no tags 

You are given a set of N sticks and are required to partition them into groups of exactly 3 sticks each. While doing so, you can leave out any number of sticks out of these groups (in particular, no groups may be formed). One condition needs to be met: sticks in each group need to form a triangle. A triangle can be constructed if sum of any two sticks lengths is greater than the third length.

Your are required to partition the sticks so that the sum of triangle areas from all the groups is maximized.

Input

Very first line of the input contains integer T: number of test cases (1 <= T <= 5).

For each test case, first line contains integer N: number of sticks. (1 <= N <= 15).

Second line contains N space separated integers: the lengths li of the sticks. (1 <= li <= 10^3, 1 <= i <= N). 

Output

For each test case, output the maximal area in a separate line. Round value to exactly 6 decimal places. Always print exactly 6 decimal places.

Example

Input:
3
3
7 8 5
4
7 8 6 3
3
7 2 1

Output:
17.320508
20.333163
0.000000

hide comments
Miguel Oliveira: 2013-08-20 12:25:34

@Lakshman, the answer is 397819.553484

[Lakshman]: 2013-08-19 14:52:50

Getting WA what is the output for.
13
7 2 1 21 22 23 1000 999 888 7 8 6 3

[Lakshman]: 2013-08-19 14:52:17

@Praveen123 can you please tell me where my code fails?


Added by:praveen123
Date:2013-08-05
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource: