1472_C. Long Jumps
Polycarp found under the Christmas tree an array a of n elements and instructions for playing with it: 

  * At first, choose index i (1 ≤ i ≤ n) — starting position in the array. Put the chip at the index i (on the value a_i). 
  * While i ≤ n, add a_i to your score and move the chip a_i positions to the right (i.e. replace i with i + a_i). 
  * If i > n, then Polycarp ends the game. 



For example, if n = 5 and a = [7, 3, 1, 2, 3], then the following game options are possible: 

  * Polycarp chooses i = 1. Game process: i = 1 \overset{+7}{\longrightarrow} 8. The score of the game is: a_1 = 7. 
  * Polycarp chooses i = 2. Game process: i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8. The score of the game is: a_2 + a_5 = 6. 
  * Polycarp chooses i = 3. Game process: i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6. The score of the game is: a_3 + a_4 = 3. 
  * Polycarp chooses i = 4. Game process: i = 4 \overset{+2}{\longrightarrow} 6. The score of the game is: a_4 = 2. 
  * Polycarp chooses i = 5. Game process: i = 5 \overset{+3}{\longrightarrow} 8. The score of the game is: a_5 = 3. 



Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array a.

The next line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — elements of the array a.

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

Output

For each test case, output on a separate line one number — the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from 1 to n in such a way as to maximize his result.

Example

Input


4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1


Output


7
6
1000
5

Note

The first test case is explained in the statement.

In the second test case, the maximum score can be achieved by choosing i = 1.

In the third test case, the maximum score can be achieved by choosing i = 2.

In the fourth test case, the maximum score can be achieved by choosing i = 1.
```python
for _ in range(int(input())):
    n = int(input())
    array = list(map(int, input().split()))
    for i in range(n-1, -1, -1):
        if i+array[i]<=n-1:
            array[i] += array[i+array[i]]
    print(max(array))
```