G. Yura and Deadlines
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Yura has $$$n$$$ homework assignments. For each assignment, its weight $$$a_i$$$ is known — the number of course points Yura will receive if he completes it.

Yura wants to choose a subset of assignments to maximize the total number of points. However, he has one problem: some assignments are too time-consuming. If Yura works on two assignments at positions $$$i$$$ and $$$j$$$ ($$$i \neq j$$$), there must be enough other assignments between them; otherwise, he will get distracted and fail to complete them.

Formally, for any two chosen assignments with indices $$$i$$$ and $$$j$$$, the following condition must hold: $$$|i - j| \gt \max(a_i, a_j)$$$.

Find the maximum total weight Yura can obtain by choosing a subset of assignments satisfying this condition.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum total weight of the selected assignments.

Example
Input
3
5
3 1 1 1 3
3
2 1 2
7
4 1 5 1 1 4 1
Output
6
2
8
Note

In the first example, it is optimal to choose assignments with indices $$$1$$$ and $$$5$$$.

In the third example, it is optimal to choose assignments with indices $$$1$$$ and $$$6$$$.