Cho ~n~ nam châm trên trục tọa độ ~Ox~, nam châm thứ ~i~ có tọa độ ~x_i~. Các nam châm được đánh số từ ~1~ đến ~n~ theo tọa độ tăng dần, đồng thời có kích thước không đáng kể. Bạn có thể thực hiện phép toán sau với số lần tùy ý:

• Chọn hai nam châm ~i~ và ~j~ (~i < j~) và số thực ~t~.

• Kích hoạt hai nam châm ~i~ và ~j~ với tham số ~t~. Khi đó, nam châm ~i~ sẽ di chuyển đến tọa độ ~x_i + t~, nam châm ~j~ sẽ di chuyển đến tọa độ ~x_j - t~.

• Các nam châm không được phép vượt mặt nhau trong quá trình di chuyển. Nói cách khác, ~t \le \min\left(\frac{x_j - x_i}{2}, x_{i+1} - x_i, x_j - x_{j-1}\right)~.

• Bạn sẽ nhận được điểm số ~t~.

Hãy tìm tổng điểm số tối đa có thể nhận được sau khi thực hiện phép toán trên.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \le t \le 100~) là số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên ~n~ (~2 \le n \le 2 \cdot 10^5~) — số lượng nam châm.

Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \ldots, x_n~ (~0 \le x_1 < x_2 < \ldots < x_n \le 10^6~) — tọa độ của các viên nam châm.

Dữ liệu đảm bảo tổng ~n~ trong tất cả các test case không quá ~2 \cdot 10^5~.

Output

Với mỗi test case, in ra một số thực duy nhất là tổng điểm lớn nhất có thể nhận được.

Định nghĩa ~J~ là đáp án của ban tổ chức, ~P~ là đáp án mà bạn đưa ra. Đáp án của bạn sẽ được cho là đúng nếu như sai số tương đối hoặc tuyệt đối so với đáp án của ban tổ chức không vượt quá ~10^{-6}~, hay ~\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

Ở ví dụ thứ nhất, ta sẽ chọn hai nam châm ở tọa độ ~1~ và ~4~ với ~t = 1.5~. Tọa độ sau khi thực hiện phép toán là ~[2.5, 2.5]~. Ta không thực hiện được thêm phép toán nào khác, nên tổng điểm số lớn nhất là ~1.5~.

Ở ví dụ thứ hai, ta sẽ thực hiện phép toán như sau:

• Chọn hai nam châm ở tọa độ ~0~ và ~1~ và ~t = 0.5~. Tọa độ sau khi thực hiện phép toán là ~[0.5, 0.5, 2]~

• Chọn hai nam châm ở tọa độ ~0.5~ và ~2~ với ~t = 0.5~. Tọa độ sau khi thực hiện phép toán là ~[0.5, 1, 1.5]~

• Chọn hai nam châm ở tọa độ ~0.5~ và ~1~ với ~t = 0.25~. Tọa độ sau khi thực hiện phép toán là ~[0.75, 0.75, 1.5]~

• Chọn hai nam châm ở tọa độ ~0.75~ và ~1.5~ với ~t = 0.25~. Tọa độ sau khi thực hiện phép toán là ~[0.75, 1, 1.25]~

• ...

Tổng điểm số là ~0.5 + 0.5 + 0.25 + 0.25 + ... = 2 \times \sum_{x=1}^{\infty} \left( \frac{1}{2} \right)^x = 2~.