Background

You are right, but when Little $\iiint$ was playing CF, he mistook Earn or Unlock as the weird parody below, wasted 2 hours, and had to leave with regret. Hope everyone can take this as a warning.

Problem Description

Given an array $a$ of length $n$, initially only $a_1$ is unlocked. Now there is an integer $i$ with initial value $1$. Little $\iiint$ plays a game on this array:

• If $a_i$ is not unlocked, the game ends.
• Otherwise, he can either set $a_{i+1\sim i+a_i}$ to unlocked, or gain $a_i$ coins (if $a_i=0$ then he cannot unlock any element), and then increase $i$ by $1$.

Please find the maximum number of coins you can obtain after the game ends.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains a positive integer $n$.

The next line contains $n$ non-negative integers $a_{1\sim n}$.

Output Format

For each test case, output one number per line, representing the answer.

3
2
1 2
5
2 4 5 0 1
4
0 4 4 4

2
9
0

1
10
1 1 4 5 1 4 1 9 1 9

26

Hint

Sample 1 Explanation

For the first test case, you can unlock $a_2$, then gain $a_2$ coins. For the third test case, you cannot unlock $a_2$, so you can only gain $0$ coins.

For the second test case, you can unlock $a_2,a_3$ and gain $9$ coins.

Sample 2 Explanation

Using positions $1,2,3,6$ for unlocking is the optimal strategy.

Constraints

For $100\%$ of the data, $1\le n\le10^5$, $0\le a_i\le10^5$, $T\le 5$.

Translated by ChatGPT 5