Cho dãy số gồm \(n\) (\(n \le 10^6\)) số nguyên không âm \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^9\)). Ta xóa các số trong dãy theo thứ tự bất kỳ, khi đó xảy ra \(1\) trong \(3\) trường hợp sau:

• Số bị xóa kề với \(2\) số chưa bị xóa ở \(2\) bên. Giả sử \(2\) số chưa bị xóa là \(x\) và \(y\) thì điểm được tăng thêm một lượng là \(\frac{x + y}{2}\), lưu ý là không làm tròn.
• Số bị xóa kề với \(1\) số chưa bị xóa. Giả sử số chưa bị xóa là \(x\) thì điểm được tăng thêm \(x\).
• Số bị xóa không kề với bất kỳ số nào chưa bị xóa. Khi đó điểm số giữ nguyên.

In ra số điểm lớn nhất có thể đạt được khi xóa hết cả \(n\) số.

Input

• Dòng đầu gồm số nguyên dương \(t\) (\(t \le 10\)) là số bộ dữ liệu.
• Trong \(t\) bộ dữ liệu:
  • Dòng đầu mỗi bộ dữ liệu gồm số nguyên dương \(n\).
  • Dòng thứ \(2\) gồm \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\).

Output

• \(t\) dòng là kết quả của \(t\) bộ dữ liệu, làm tròn đến chữ số đầu tiên ở hàng thập phân.

Example

2
4
2 0 1 4
3
1 2 3

5.5
5.0

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^2\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^6\).