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 l_i of the sticks. (1 <= l_i <= 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