No submission language available for this problem.

Description

Input

The first line contains a single integer $t$ ($1 \le t \le 10^3$)— the number of test cases. Each test case consists of two lines.

The first line contains a single integer $n$ ($2 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot10^5$.

Output

For each test case, print a single value — the maximum value that Ezzat can achieve.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.

Samples

4
3
3 1 2
3
-7 -6 -6
3
2 2 2
4
17 3 5 -3

4.500000000
-12.500000000
4.000000000
18.666666667

Note

In the first test case, the array is $[3, 1, 2]$. These are all the possible ways to split this array:

• $a = [3]$, $b = [1,2]$, so the value of $f(a) + f(b) = 3 + 1.5 = 4.5$.
• $a = [3,1]$, $b = [2]$, so the value of $f(a) + f(b) = 2 + 2 = 4$.
• $a = [3,2]$, $b = [1]$, so the value of $f(a) + f(b) = 2.5 + 1 = 3.5$.

Therefore, the maximum possible value $4.5$.

In the second test case, the array is $[-7, -6, -6]$. These are all the possible ways to split this array:

• $a = [-7]$, $b = [-6,-6]$, so the value of $f(a) + f(b) = (-7) + (-6) = -13$.
• $a = [-7,-6]$, $b = [-6]$, so the value of $f(a) + f(b) = (-6.5) + (-6) = -12.5$.

Therefore, the maximum possible value $-12.5$.