Cho 1 thanh gỗ có chiều dài \(n\) (mét) và bảng giá tất cả các khúc gỗ có kích thước bé hơn hoặc bằng \(n\). Xác định giá trị lớn nhất có thể đạt được bằng cách cắt thanh gỗ thành khúc và bán các khúc gỗ đó.

Input

• Dòng đầu tiên là số bộ test \(t\).
• \(2 \times t\) dòng tiếp theo mô tả \(t\) bộ test. Mỗi bộ test gồm có 2 dòng: Dòng đầu là số \(n\). Dòng thứ hai là giá bán các khúc gỗ có chiều dài lần lượt từ \(1\) đến \(n\) cách nhau bởi khoảng trắng.

Output

• Với mỗi bộ test, output trên 1 dòng riêng biệt giá trị lớn nhất có thể đạt được khi bán gỗ.

Constraints

• \(1 \le n \le 10^5\)
• Giá bán các khúc gỗ là số nguyên dương không lớn hơn \(10^3\).

Example

Sample input

2
8
1 5 8 9 10 17 17 20
8
3 5 8 9 10 17 17 20

Sample output

22
24