A. Hinge Arch
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a toy consisting of $$$n$$$ sticks of varying lengths connected in order in a row by hinges. The sticks can be rotated arbitrarily around the hinges and are allowed to overlap.

You want to create an arch with these sticks. To do this, you will place the two endpoints of the structure anywhere on the surface of a table and position the rest of the sticks and hinges arbitrarily. You can ignore gravity and assume the sticks and hinges have zero width. Sticks are allowed to overlap and/or intersect with each other but may not intersect with the table. Note that the order of the sticks is fixed and cannot be changed. One possible arch is shown here:

You want to maximize the height of the arch, defined as the maximum distance from the surface of the table to a point on the arch (this is shown as the dotted red line above). What is the maximum height you can achieve?

Input

The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 500$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n \le 1000$$$) — the number of sticks in the structure.

The second line of each test case will contain $$$n$$$ integers $$$l_1, l_2, \cdots l_n$$$ ($$$1 \le l_i \le 1000$$$) — the lengths of each of the sticks, in order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, output one line containing a single number — the maximum possible height of the arch.

Your answer is considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$. Namely, if your answer is $$$a$$$, and the judge's answer is $$$b$$$, then your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$$$.

Example
Input
5
5
1 2 4 2 3
3
1 4 1
2
4 4
6
1 6 13 4 100 2
3
1 2 3
Output
5.000
1.000
4.000
24.000
3.000
Note

The first test case uses the sticks from the picture above. The arch shown above is not optimal.

This is one possible maximal arch for the second test case:

This is one possible maximal arch for the third test case:

Note that the sticks are allowed to fully overlap.