Antenna repair (Large)

The adventurer Pascal found an alien communication device left behind by an ancient civilization and worked out how to use it. The antenna of the device is built from K straight rods called elements, each made of a special material. One end of an element is its plus pole and the other end is its minus pole. The elements are numbered from 1 to K.

The antenna works only if it is assembled so that all four conditions below hold.

• Every element lies in the same plane.
• The plus poles of all elements meet at one point, called the junction.
• The junction is the only place where elements overlap.
• The angle between two neighboring elements is $360/K$ degrees for every such pair.

The elements sit at equal angles around the junction, so there are exactly K neighboring pairs. For each pair, take the triangle formed by the junction and the two minus poles of that pair. The strength of the antenna is the sum of the areas of those K triangles.

Find the arrangement that maximizes the strength and report that strength.

Elements are thin enough that their thickness can be ignored. You cannot cut an element, and you cannot join several elements into one.

The first line holds a positive integer T, the number of test cases. Each test case is given in the following format.

K
E1 E2 ... EK

K is the number of elements, and $E_i$ is a positive integer, the length of the i-th element.

Constraints

• $1 \le T \le 100$
• $3 \le K \le 1000$
• $1 \le E_i \le 1000$

For each test case, print one line in the following format.

Case #X: P

X is the test case number starting from 1, and P is the maximum strength. Round P to nine digits after the decimal point and print all nine digits, including trailing zeros.