Problem Background

You are correct, but little $\iiint$ mistakenly read "Earn or Unlock" on Codeforces as something bizarre, resulting in a loss of 2 hours and a regretful exit. Hopefully, others can learn from this experience.

Problem Description

Given an array \(a\) of length \(n\), initially only \(a_1\) is unlocked. There is an integer \(i\), initially set to 1. Little $\iiint$ is playing a game with this array:

• If \(a_i\) is not unlocked, the game ends.
• Otherwise, he can either unlock \(a_{i+1 \sim i+a_i}\) or earn \(a_i\) coins (if \(a_i = 0\), no elements can be unlocked), and then increment \(i\) by 1.

Please calculate the maximum number of coins you can earn after the game ends.

Input Format

This problem contains multiple test cases.

The first line contains an integer \(T\), representing 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 line containing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
9
0

Sample Input #2

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

Sample Output #2

26

Notes

Sample 1 Explanation

For the first set of data, you can unlock \(a_2\) and then earn \(a_2\) coins. For the third set of data, you cannot unlock \(a_2\), so you can only earn 0 coins.

For the second set of data, you can unlock \(a_2\) and \(a_3\), and earn 9 coins.

Sample 2 Explanation

Using the 1st, 2nd, 3rd, and 6th positions for unlocking is the optimal strategy.

Data Range

For 100% of the data, \(1 \le n \le 10^5\), \(0 \le a_i \le 10^5\), \(T \le 5\).

见题面 Input 部分

见题面 Output 部分