Xét trò chơi như sau: Máy tính tạo ngẫu nhiên một dãy số nguyên không âm a1,a2,..., an. Số ai có một số liền kề là số a2, số an, có một số liên kề là s an-1, các số khác có hai số liền kề. Người chơi sẽ được tổng điểm thưởng khi thực hiện liên tiếp một trong các hành động chọn số dưới đây:

1) Chọn một số có hai số liền kề, điểm thưởng là trung bình cộng của hai số liền kề, sau hành động này số được chọn bị xóa;

2) Chọn một số có một số liền kề (có thể do các lượt chọn trước đã xóa số kề hoặc do số nằm ở vị trí 1 hoặc vị trí ban đầu), điểm thưởng là số liền kề, sau hành động này số được chọn bị xóa;

3) Chọn một số không có số liền kề, khi đó sẽ không được điểm thưởng nào, sau hành động này số được chọn bị xóa.

Yêu cầu: Hãy tìm cách chọn số ) để tổng điểm thưởng là lớn nhất.

Dữ liệu: Vào từ file văn bản RGAME.INP gồm:

Dòng đầu chứa số nguyên T là số bộ dữ liệu. Tiếp theo là T nhóm dòng, mỗi nhóm có định dạng sau:

• Dòng đầu của nhóm chứa số nguyên n

• Dòng thứ hai của nhóm chứa n số nguyên không âm mô tả dãy số ban đầu. Các số không vượt quá 10^9.

Tổng các số n không vượt quá 10^6.

Kết quả: ghi ra file văn bản RGAME.OUT gồm T dòng, mỗi dòng chứa một số thực (với độ chính xác một chữ số sau dấu chấm) là tổng điểm lớn nhất đạt được tương ứng với từng bộ dữ liệu.

Input:

2
3
1 2 3
4
2 0 1 4

Output:

5
5.5

Ràng buộc:

• Subtask 1: n ≤ 8;

• Subtask 2: n ≤ 100;

• Subtask 3: n ≤ 10^6.