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.

inputFormat

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.

outputFormat

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.

样例

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

7
6
1000
5

</p>