Given ~n~ magnets on the ~Ox~ coordinate axis, the ~i~-th magnet has coordinate ~x_i~. The magnets are numbered from ~1~ to ~n~ in increasing order of coordinates and have negligible size. You can perform the following operation any number of times:

• Choose two magnets ~i~ and ~j~ (~i < j~) and a real number ~t~.

• Activate magnets ~i~ and ~j~ with parameter ~t~. Then, magnet ~i~ will move to coordinate ~x_i + t~, and magnet ~j~ will move to coordinate ~x_j - t~.

• The magnets are not allowed to pass each other during the movement. In other words, ~t \le \min\left(\frac{x_j - x_i}{2}, x_{i+1} - x_i, x_j - x_{j-1}\right)~.

• You will receive a score of ~t~.

Find the maximum total score that can be obtained after performing the operations.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 100~) which is the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~2 \le n \le 2 \cdot 10^5~) — the number of magnets.

The second line contains ~n~ integers ~x_1, x_2, \ldots, x_n~ (~0 \le x_1 < x_2 < \ldots < x_n \le 10^6~) — the coordinates of the magnets.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

Output

For each test case, output a single real number which is the maximum total score that can be obtained.

Let ~J~ be the answer from the judges, and ~P~ be the output you provide. Your output will be considered correct if the relative or absolute error compared to the judges' answer does not exceed ~10^{-6}~, i.e., ~\displaystyle\frac{|P - J|}{\max\{1, |J|\}} \le 10^{-6}~.

Scoring

Sample Input 1

2
2
1 4
3
0 1 2

Sample Output 1

1.5
2

Notes

In the first example, we will choose two magnets at coordinates ~1~ and ~4~ with ~t = 1.5~. The coordinates after performing the operation are ~[2.5, 2.5]~. We cannot perform any other operations, so the maximum total score is ~1.5~.

In the second example, we will perform the operations as follows:

• Choose two magnets at coordinates ~0~ and ~1~ and ~t = 0.5~. The coordinates after performing the operation are ~[0.5, 0.5, 2]~

• Choose two magnets at coordinates ~0.5~ and ~2~ with ~t = 0.5~. The coordinates after performing the operation are ~[0.5, 1, 1.5]~

• Choose two magnets at coordinates ~0.5~ and ~1~ with ~t = 0.25~. The coordinates after performing the operation are ~[0.75, 0.75, 1.5]~

• Choose two magnets at coordinates ~0.75~ and ~1.5~ with ~t = 0.25~. The coordinates after performing the operation are ~[0.75, 1, 1.25]~

• ...

The total score is ~0.5 + 0.5 + 0.25 + 0.25 + ... = 2 \times \sum_{x=1}^{\infty} \left( \frac{1}{2} \right)^x = 2~.