Cá Xanh Nhỏ đang chơi Slay the Spire II và đã chọn nhân vật "Silent".

Cá Xanh Nhỏ hiện cần chiến đấu với một "Người Bạn Chiến Đấu" (Battle Friend). Ban đầu, cả số tầng "Độc" (Poison) của Người Bạn Chiến Đấu và cấp độ "Chất Xúc Tác" (Accelerant) của bạn đều bằng $0$. Trong mỗi lượt của $n$ lượt tiếp theo, các sự kiện sau sẽ lần lượt xảy ra:

1. Sử dụng "Độc Chết Người" (Deadly Poison): tăng số tầng Độc của Người Bạn Chiến Đấu thêm $x_i$.

2. Chọn có sử dụng "Chất Xúc Tác" hay không: chọn có tăng cấp độ Chất Xúc Tác của bạn thêm $1$ hay không.

3. Kích hoạt hiệu ứng Độc: gọi cấp độ Chất Xúc Tác của bạn là $t$, lặp lại sự kiện sau $t$ lần:

   • Gọi số tầng Độc của Người Bạn Chiến Đấu là $x$. Nếu $x > 0$, gây $x$ sát thương lên Người Bạn Chiến Đấu và giảm số tầng Độc đi $1$; ngược lại, nếu $x = 0$, không có gì xảy ra.

Lưu ý rằng cả số tầng Độc và cấp độ Chất Xúc Tác đều được giữ nguyên qua các lượt và không biến mất.

Cá Xanh Nhỏ muốn tối đa hóa tổng sát thương gây ra cho Người Bạn Chiến Đấu trong $n$ lượt này. Hãy in ra tổng sát thương lớn nhất đó.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T$), biểu thị số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 5000$).

Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), biểu thị số tầng Độc tăng thêm của Người Bạn Chiến Đấu trong mỗi lượt.

Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ test không vượt quá $10^6$, và tổng của $n^2$ trong tất cả các bộ test không vượt quá $10^8$.

Kết quả

Với mỗi bộ test, in ra một dòng chứa một số nguyên là tổng sát thương lớn nhất có thể gây ra cho Người Bạn Chiến Đấu trong tất cả các lượt.

Ví dụ

Ví dụ đầu vào 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Ví dụ đầu ra 1

33
11
750
725