Polycarp found under the Christmas tree an array $a$ of $n$ elements and instructions for playing with it:

At first, choose index $i$ ($1 \leq i \leq n$) — starting position in the array. Put the chip at the index $i$ (on the value $a_i$).

While $i \leq 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 \leq t \leq 10^4$) — the number of test cases. Then $t$ test cases follow.

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

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

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 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.


-----Examples-----

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$.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Graph algorithms


Solutions:
import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
uu = t
while t > 0:
	t -= 1
	n = fi()
	a = li()
	d = [0] * n
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			d[i] = a[i] + d[i + a[i]]
		else:
			d[i] = a[i]
	print(max(d))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a
	for i in range(n)[::-1]:
		if i + a[i] < n:
			b[i] += b[i + a[i]]
	print(max(b))


t = int(input())
_scores = [0 for i in range(0, t)]
for i in range(0, t):
	n_input = int(input())
	a_input = input().split(' ')[:n_input]
	a = [int(ai) for ai in a_input]
	_accumulator = [0 for _ in range(0, n_input)]
	for chip in reversed(range(0, n_input)):
		if chip + a[chip] < n_input:
			_accumulator[chip] = a[chip] + _accumulator[chip + a[chip]]
		else:
			_accumulator[chip] = a[chip]
	_scores[i] = max(_accumulator)
for score in _scores:
	print(score)


import sys
import math
import copy
from collections import deque, Counter
input = sys.stdin.readline
dp = {}

def findValue(i, a):
	global dp
	ans = 0
	if i in dp:
		return ans
	while i <= len(a):
		ans += a[i - 1]
		i = i + a[i - 1]
		if i in dp:
			return ans
		dp[i] = 0
	return ans

def solve():
	dp.clear()
	n = int(input())
	a = list(map(int, input().split()))
	ans = -1
	for i in range(1, n + 1):
		ans = max(ans, findValue(i, a))
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def isPossible(arr, n):
	j = 0
	for i in range(n - 1, -1, -1):
		if arr[i] + i + 1 > n:
			continue
		else:
			arr[i] += arr[i + arr[i]]
	return max(arr)
for i in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	print(isPossible(y, len(y)))


for u in range(int(input())):
	n = int(input())
	x = [int(w) for w in input().split()]
	t = 0
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		temp = 0
		if x[i] + i < n:
			ans[i] = x[i] + ans[i + x[i]]
			temp = ans[i]
		else:
			ans[i] = x[i]
			temp = ans[i]
		t = max(t, temp)
	print(t)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			a[i] += a[i + a[i]]
	print(max(a))


for _ in range(0, int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	for i in range(n, 0, -1):
		if i + a[i] > n:
			continue
		a[i] += a[i + a[i]]
	print(max(a))


for _ in range(int(input())):
	n = int(input())
	A = [0] + list(map(int, input().split()))
	M = [0] * (n + 1)
	for i in range(1, n + 1):
		S = []
		while i <= n and M[i] == 0:
			S.append(i)
			i += A[i]
		m = 0
		if S and M[S[-1]] != 0:
			m = M[S.pop()]
		while S:
			s = S.pop()
			if s <= n:
				m += A[s]
			M[s] = m
	print(max(M))


for t in range(int(input())):
	n = int(input())
	d = [int(i) for i in input().split()]
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		aa = d[i]
		if i + aa >= n:
			dp[i] = aa
		else:
			dp[i] = aa + dp[i + aa]
	print(max(dp))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	ans[-1] = a[-1]
	for i in range(n - 2, -1, -1):
		ans[i] = a[i] + (ans[i + a[i]] if i + a[i] < n else 0)
	print(max(ans))


def encontrar_melhor_score(a):
	n = len(a)
	S = [0] * n
	melhor_score = 0
	for i in range(n - 1, -1, -1):
		score = a[i]
		if i + a[i] < n:
			score += S[i + a[i]]
		if score > melhor_score:
			melhor_score = score
		S[i] = score
	print(melhor_score)
t = int(input())
for i in range(t):
	n = input()
	a = [int(x) for x in input().split(' ')]
	encontrar_melhor_score(a)


import sys
import heapq
input = sys.stdin.readline
from collections import Counter, defaultdict

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def main():
	length = inp()
	array = inlt()
	for i in range(length - 1, -1, -1):
		newPlace = i + array[i]
		if newPlace < length:
			array[i] += array[newPlace]
	print(max(array))
t = inp()
for _ in range(t):
	main()


def get_input():
	arr = input().split()
	res = []
	for i in arr:
		res.append(int(i))
	return res

def maximum_score(arr, n):
	value_array = [0] * n
	for i in range(n - 1, -1, -1):
		if arr[i] + i > n - 1:
			value_array[i] = arr[i]
		else:
			value_array[i] = arr[i] + value_array[arr[i] + i]
	return max(value_array)
no_tests = int(input())
res = []
for i in range(no_tests):
	n = int(input())
	arr = get_input()
	res.append(maximum_score(arr, n))
for each in res:
	print(each)


t = int(input())
result = []
for b in range(t):
	n = int(input())
	tab = list(map(int, input().split(' ')))
	test = []
	for i in range(n - 1, -1, -1):
		score = i + tab[i]
		if score > n - 1:
			test.append(tab[i])
		else:
			test.append(test[n - 1 - score] + tab[i])
	result.append(max(test))
for i in result:
	print(i)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()
from collections import deque, Counter, defaultdict as dft
from heapq import heappop, heappush
from math import log, sqrt, factorial, cos, tan, sin, radians, log2, ceil, floor
from bisect import bisect, bisect_left, bisect_right
from decimal import *
import sys, threading
from itertools import permutations, combinations
from copy import deepcopy
input = sys.stdin.readline
ii = lambda : int(input())
si = lambda : input().rstrip()
mp = lambda : map(int, input().split())
ms = lambda : map(str, input().strip().split(' '))
ml = lambda : list(mp())
mf = lambda : map(float, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)
spf = [0 for i in range(MAXN)]

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
alphs = 'abcdefghijklmnopqrstuvwxyz'
mxn = 10 ** 20

def solve():
	n = ii()
	ls = ml()
	mx = 0
	for i in range(n - 1, -1, -1):
		if i + ls[i] < n:
			ls[i] += ls[ls[i] + i]
	print(max(ls))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
tc = ii()
for i in range(tc):
	solve()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		maxx = [0] * n
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				maxx[i] = arr[i]
			elif i + arr[i] < n:
				maxx[i] = arr[i] + maxx[i + arr[i]]
			else:
				maxx[i] = arr[i]
		get_print_int(max(maxx))
solve()


import sys, os
from math import sqrt, gcd, ceil, log, floor
from math import factorial as fact
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
MOD = 10 ** 9 + 7

def f(a):
	c = 0
	while a % 2 == 0:
		c += 1
		a //= 2
	return c

def main():
	ans_ = []
	for i in range(int(input())):
		n = int(input())
		arr = read()
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			if i + arr[i] >= n:
				dp[i] = arr[i]
			else:
				dp[i] += arr[i] + dp[i + arr[i]]
		ans_.append(max(dp))
	for i in ans_:
		print(i)
main()


index_f_value = dict()

def get_value(array, index):
	if index == 0:
		return 0
	global index_f_value
	if not index in index_f_value:
		if index + int(array[index]) < len(array):
			index_f_value.update([(index, int(array[index]) + get_value(array, index + int(array[index])))])
		else:
			index_f_value.update([(index, int(array[index]))])
	return index_f_value[index]
in_length = int(input())
final_ouput = []
for i in range(in_length):
	index_f_value = dict()
	length = int(input())
	inputs = input().split()
	inputs.insert(0, 0)
	max_val = 0
	for (j, el) in enumerate(inputs):
		index = length - j
		val = get_value(inputs, index)
		if val > max_val:
			max_val = val
	final_ouput.append(max_val)
for out in final_ouput:
	print(out)


tests = int(input())
for _ in range(tests):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		transition = i + a[i]
		if transition < n:
			a[i] += a[transition]
	print(max(a))


def inp_list_of_int():
	return list(map(int, input().split()))

def inp_int():
	return int(input())

def inp_str():
	return input()

def inp_split():
	return input().split()
for _ in range(inp_int()):
	n = inp_int()
	arr = inp_list_of_int()
	dp = [0] * n
	for x in range(n - 1, -1, -1):
		if x + arr[x] > n - 1:
			dp[x] = arr[x]
		else:
			dp[x] = arr[x] + dp[x + arr[x]]
	print(max(dp))


import sys
input = sys.stdin.readline
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] = a[i]
		if i + a[i] <= n - 1:
			dp[i] += dp[i + a[i]]
	print(max(dp))


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	for i in range(len(A) - 1, -1, -1):
		if i + A[i] >= n:
			A[i] = A[i]
		else:
			A[i] = A[i + A[i]] + A[i]
	print(max(A))


t = int(input())
for tt in range(t):
	n = int(input())
	f = [0] + list(map(int, input().split()))
	d = [0 for i in range(n + 2)]
	for i in range(1, len(f)):
		d[min(n + 1, i + f[i])] = max(d[i] + f[i], d[min(n + 1, i + f[i])])
	print(d[-1])


def answer(n, ary):
	v = [False] * (n + 1)
	v[0] = True
	ary.insert(0, 0)
	max_score = 0
	for i in range(1, n + 1, 1):
		score = 0
		while v[i] == False:
			v[i] = True
			score += ary[i]
			i += ary[i]
			if i > n:
				i = 0
		if score > max_score:
			max_score = score
	return max_score

def main():
	t = int(input())
	n = [0] * t
	ary = [0] * t
	for j in range(t):
		n[j] = int(input())
		ary[j] = [int(i) for i in input().split()]
	for j in range(t):
		print(answer(n[j], ary[j]))
main()


for i in range(int(input())):
	size = int(input())
	the_arr = list(map(int, input().split()))
	for j in range(size - 1, -1, -1):
		if j + the_arr[j] <= size - 1:
			the_arr[j] += the_arr[j + the_arr[j]]
	print(max(the_arr))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		if i + l[i] >= n:
			ans[i] = l[i]
		else:
			ans[i] = ans[i + l[i]] + l[i]
	print(max(ans))


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		if i + arr[i] < n:
			arr[i] += arr[i + arr[i]]
	print(max(arr))
for _ in range(int(input())):
	solve()


def find_max_leap(n, a):
	i = n - 1
	b = [0] * n
	while i >= 0:
		b[i] = a[i] + (b[i + a[i]] if i + a[i] < n else 0)
		i -= 1
	return max(b)
t = int(input())
for t_i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(find_max_leap(n, a))


def find_max_score(array, n):
	max_score = [float('-inf')] * n
	max_score[-1] = array[-1]
	for i in range(n - 2, -1, -1):
		if i + array[i] > n - 1:
			max_score[i] = array[i]
		else:
			max_score[i] = array[i] + max_score[i + array[i]]
	return max(max_score)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	result = find_max_score(a, n)
	print(result)


def main():
	from sys import stdin, stdout
	input = stdin.readline
	print = stdout.write
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		b = [0 for x in range(n)]
		for index in range(n - 1, -1, -1):
			score = a[index]
			score += b[index + score] if index + score < n else 0
			b[index] = score
		print(f'{max(b)}\n')
main()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0] * n
	for i in reversed(range(n)):
		dp[i] = a[i]
		j = i + a[i]
		if j < n:
			dp[i] += dp[j]
	print(max(dp))


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
out = []
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	r = [0]
	m = 0
	for i in range(n - 1, -1, -1):
		x = n - i - a[i]
		if x < 0:
			x = 0
		r.append(r[x] + a[i])
		if r[-1] > m:
			m = r[-1]
	out.append(str(m))
print('\n'.join(out))


import sys
import math

def ints():
	return list(map(int, sys.stdin.readline().strip().split()))
T = int(input())
while T:
	T -= 1
	n = int(input())
	ls = ints()
	c = []
	j = 0
	for item in ls[::-1]:
		if item > j:
			c.append(item)
		else:
			c.append(item + c[j - item])
		j += 1
	print(max(c))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	dp = [0 for _ in range(n)]
	dp[-1] = s[-1]
	for i in range(n - 1, -1, -1):
		dp[i] = s[i]
		j = i + s[i]
		if j < n:
			dp[i] += dp[j]
	print(max(dp))


def get_max_points(v):
	lookup = [0] * len(v)
	for i in range(len(v) - 1, -1, -1):
		lookup[i] = v[i]
		j = i + v[i]
		if j < len(v):
			lookup[i] += lookup[j]
	return max(lookup)

def main():
	t = int(input())
	for i in range(t):
		input()
		v = [int(e) for e in input().split(' ')]
		print(get_max_points(v))
main()


def process(a):
	N = len(a)
	dp = [0] * N
	for i in range(N - 1, -1, -1):
		dp[i] = a[i] + (dp[i + a[i]] if i + a[i] < N else 0)
	return max(dp)
t = int(input())
ans = []
for _ in range(t):
	n = input()
	a = [int(i) for i in input().split(' ')]
	ans.append(process(a))
for i in ans:
	print(i)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	b = a[:]
	for i in range(n):
		x = i + a[i]
		try:
			b[x] = max(b[x], b[i] + a[x])
		except:
			pass
	print(max(b))


def solve():
	l = int(input())
	lst = list(map(int, input().strip().split()))[:l]
	dp = [0 for i in range(l)]
	for i in range(l - 1, -1, -1):
		dp[i] = lst[i]
		j = i + lst[i]
		if j < l:
			dp[i] += dp[j]
	return max(dp)
n = int(input())
for i in range(n):
	print(solve())


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}

	def f(i):
		if i >= n:
			return 0
		if i not in d:
			d[i] = a[i] + f(i + a[i])
		return d[i]
	print(max((f(i) for i in reversed(range(n)))))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	summ = [0] * n
	for i in range(n - 1, -1, -1):
		summ[i] = a[i] + (summ[i + a[i]] if i + a[i] < n else 0)
	print(max(summ))


test = int(input())
for _ in range(test):
	n = int(input())
	d = [0] * n
	a = list(map(int, input().split()))
	choix = False
	for i in range(n - 1, -1, -1):
		if a[i] + i < n:
			d[i] = d[a[i] + i] + a[i]
		else:
			d[i] = a[i]
	print(max(d))


test = int(input())
while test:
	n = int(input())
	li = list(map(int, input().split()))
	dp = [0 for i in range(n)]
	for i in reversed(range(n)):
		if i + li[i] >= n:
			dp[i] = li[i]
		else:
			dp[i] = li[i] + dp[i + li[i]]
	print(max(dp))
	test -= 1


import sys
import bisect as bi
import collections as cc
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n,) = I()
	ar = I()
	temp = [0] * n
	for i in range(n):
		if i + ar[i] < n:
			temp[i + ar[i]] = max(temp[i + ar[i]], temp[i] + ar[i])
	print(max((ar[i] + temp[i] for i in range(n))))


for z in range(int(input())):
	n = int(input())
	l = [0] + [int(x) for x in input().split()]
	for i in range(n, 0, -1):
		l[i] += l[i + l[i]] if i + l[i] <= n else 0
	print(max(l))


import os
from sys import stdin, stdout

def solve(tc):
	n = int(stdin.readline().strip())
	va = list(map(int, stdin.readline().split()))
	maxscore = 0
	scores = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		scores[i] = va[i]
		if i + va[i] < n:
			scores[i] += scores[i + va[i]]
		maxscore = max(maxscore, scores[i])
	print(maxscore)
tcs = 1
tcs = int(stdin.readline().strip())
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


def do(vs, dp):
	i = len(vs) - 2
	dp[-1] = vs[-1]
	while i >= 0:
		next_ind = i + vs[i]
		if next_ind >= len(vs):
			dp[i] = vs[i]
		else:
			dp[i] = vs[i] + dp[next_ind]
		i -= 1
	return max(dp)

def get_case():
	vs = []
	for i in range(200000):
		if i % 2 == 0:
			vs.append(1)
		else:
			vs.append(2)
	return vs

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		vs = list(map(int, input().split()))
		dp = [-1] * len(vs)
		print(do(vs, dp))
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if i in d:
			d[i] += l[i]
		else:
			d[i] = l[i]
		if i + l[i] < n:
			if i + l[i] in d:
				d[i + l[i]] = max(d[i + l[i]], d[i])
			else:
				d[i + l[i]] = d[i]
	print(max(d.values()))


for _ in range(int(input())):
	n = int(input())
	a = [0] + [int(x) for x in input().split()]
	for i in range(n, 0, -1):
		if i + a[i] <= n:
			a[i] += a[i + a[i]]
	print(max(a))


def main():
	from sys import stdin, stdout
	input = stdin.readline
	print = stdout.write
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		for index in range(n - 1, -1, -1):
			if a[index] + index < n:
				a[index] += a[index + a[index]]
		print(f'{max(a)}\n')
main()


from sys import stdin, stdout

def II():
	return int(stdin.readline())

def LI():
	return list(map(int, stdin.readline().split()))

def solve():
	n = II()
	a = LI()
	b = [0] * n
	for i in range(n - 1, -1, -1):
		x = a[i]
		b[i] = x
		if i + x <= n - 1:
			b[i] += b[i + x]
	ans = max(b)
	stdout.write('{}\n'.format(ans))
t = II()
for _ in range(t):
	solve()


t = int(input().strip())
while t > 0:
	t -= 1
	n = int(input().strip())
	a = [int(x) for x in input().strip().split()]
	b = [0 for _ in range(0, n)]
	maxVal = a[0]
	for i in range(n - 1, -1, -1):
		b[i] = a[i] + (0 if i + a[i] >= n else b[i + a[i]])
		maxVal = max(maxVal, b[i])
	print(maxVal)


import sys, os, getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def readint():
	return int(input())

def readstr():
	return list(map(int, input().split()))
cases = readint()

def solve(n, nums):
	scores = defaultdict(int)
	max_score = -float('inf')
	for i in range(1, n + 1):
		step = i + nums[i - 1] - 1
		if step >= n:
			max_score = max(max_score, scores[i - 1] + nums[i - 1])
		else:
			scores[step] = max(scores[step], scores[i - 1] + nums[i - 1])
	return max_score
output = []
for _ in range(int(cases)):
	n = readint()
	arr = readstr()
	output.append(solve(n, arr))
print('\n'.join(map(str, output)))


def longJumps(n: int, numbers: list):
	dp = [0] * n
	currMax = -1
	for (index, num) in enumerate(numbers):
		if index + num >= n:
			currMax = max(dp[index] + num, currMax)
		else:
			dp[index + num] = max(dp[index + num], dp[index] + num)
	return currMax
for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split()))
	print(longJumps(n, numbers))


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))


def fucker():
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in range(n - 1, -1, -1):
		if a[i] < n - i:
			a[i] += a[i + a[i]]
	print(max(a))
t = int(input())
for _ in range(0, t):
	fucker()


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	score = [0 for x in range(n)]
	mscore = 0
	for i in range(n - 1, -1, -1):
		if a[i] >= n - i:
			score[i] = a[i]
		else:
			score[i] = a[i] + score[i + a[i]]
		if score[i] > mscore:
			mscore = score[i]
	print(mscore)


from sys import stdin
input = stdin.readline
for Pythonic__Python in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1, -1, -1):
		if l[i] + i >= n:
			ans = max(ans, l[i])
		else:
			l[i] = l[i] + l[l[i] + i]
			ans = max(ans, l[i])
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	b = a[:]
	maxi = 0
	for i in range(1, n + 1):
		if b[i] + i <= n:
			a[b[i] + i] = max(a[b[i] + i], a[i] + b[b[i] + i])
		maxi = max(maxi, a[i])
	print(maxi)


import os
import sys
from io import BytesIO, IOBase

def main():
	import bisect
	import math
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7
	Max = 10 ** 6
	primes = []
	prime = [True for i in range(Max + 1)]
	p = 2
	while p * p <= Max + 1:
		if prime[p] == True:
			for i in range(p * p, Max + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, Max + 1):
		if prime[p]:
			primes.append(p)

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def solve(n, arr):
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			if i + arr[i] >= n:
				dp[i] = arr[i]
			else:
				dp[i] += arr[i] + dp[i + arr[i]]
		return max(dp)
		pass
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ans.append(solve(n, arr))
	for j in range(len(ans)):
		print(ans[j])
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


MOD = 1000000007

def si():
	return input()

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def mi():
	return map(int, input().split())

def sout(v):
	print(v, end=' ')

def d2b(n):
	return bin(n).replace('0b', '')

def twod(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def vow():
	return ['a', 'e', 'i', 'o', 'u']

def let():
	return [chr(i) for i in range(97, 123)]

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def ispow2(x):
	return x and (not x & x - 1)

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return list(factors)

def isPalindrome(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True
t = ii()
while t:
	t -= 1
	n = ii()
	a = li()
	ans = -1
	dp = [a[i] for i in range(n)]
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			dp[i] += dp[i + a[i]]
	print(max(dp))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time
sys.setrecursionlimit(5 * 10 ** 5)
inf = 10 ** 20
mod = 10 ** 9 + 7

def LI():
	return list(map(int, input().split()))

def II():
	return int(input())

def LS():
	return list(input().split())

def S():
	return input()

def div2(x):
	ans = 1
	while x % 2 == 0:
		x //= 2
		ans *= 2
	return ans

def solve():
	n = II()
	a_list = LI()
	dp = [0 for _ in range(n)]
	for i in range(0, n)[::-1]:
		dp[i] = a_list[i]
		if i + a_list[i] < n:
			dp[i] += dp[i + a_list[i]]
	return max(dp)

def main():
	t = II()
	res = list()
	for _ in range(t):
		res.append(solve())
	for ans in res:
		print(ans)
	return 0
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	r = 0
	for j in range(n - 1, -1, -1):
		if j + a[j] < n:
			a[j] += a[j + a[j]]
		r = max(r, a[j])
	print(r)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [-1 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			b[i] = a[i]
		else:
			s = a[i]
			index = i + 1 + a[i]
			while index <= n and b[index - 1] == -1:
				s = s + a[index - 1]
				index = index + a[index - 1]
			if index <= n:
				s = s + b[index - 1]
			b[i] = s
	print(max(b))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			a[i] += a[i + a[i]]
	print(max(a))


import math

def getint():
	return [int(i) for i in input().split()]

def getstr():
	return [str(i) for i in input().split()]

def solve():
	n = int(input())
	a = getint()
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		if i + a[i] > n - 1:
			dp[i] = a[i]
		else:
			dp[i] = dp[i + a[i]] + a[i]
	print(max(dp))
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	som = sum(arr)
	dp = [0 for i in range(n)]
	for i in range(n):
		dp[i] = dp[i] + arr[i]
		if i + arr[i] >= n:
			continue
		dp[i + arr[i]] = max(dp[i], dp[i + arr[i]])
	print(max(dp))


import sys
sys.setrecursionlimit(10 ** 5)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
for _ in range(ii()):
	n = ii()
	a = li()
	dp = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		dp[i] = a[i]
		if i + a[i] < n:
			dp[i] += dp[i + a[i]]
	print(max(dp))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [0] * n
	dp[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		if l[i] + i <= n - 1:
			dp[i] = l[i] + dp[i + l[i]]
		else:
			dp[i] = l[i]
	print(max(dp))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst2 = [0] * n
	lst2[0] = lst[0]
	for i in range(n):
		lst2[i] = max(lst2[i], lst[i])
		if i + lst[i] < n:
			lst2[i + lst[i]] = max(lst2[i] + lst[i + lst[i]], lst2[i + lst[i]])
	print(max(lst2))


def solve(a, n):
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			a[i] = a[i] + a[i + a[i]]
	print(max(a))
for testis in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	solve(a, n)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.insert(0, 0)
	ans = [0] * (n + 1)
	for j in range(n, -1, -1):
		ans[j] = a[j]
		if j + a[j] <= n:
			ans[j] += ans[j + a[j]]
	print(max(ans))


import math
inf = float('inf')
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] = arr[i]
		if i + arr[i] < n:
			dp[i] += dp[i + arr[i]]
	print(max(dp))


import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(a)
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			b[i] += b[i + a[i]]
	print(max(b))


for i in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	c = [0] * a
	for i in range(a - 1, -1, -1):
		if i + b[i] < a:
			c[i] = c[i + b[i]] + b[i]
		else:
			c[i] = b[i]
	print(max(c))


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	m = [0] * n
	for i in range(n - 1, -1, -1):
		m[i] = l[i]
		p = i + l[i]
		if p < n:
			m[i] = m[i] + m[p]
	print(max(m))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			a[i] += a[i + a[i]]
	res = 0
	for x in a:
		res = max(res, x)
	print(res)
t = int(input())
while t > 0:
	solve()
	t -= 1


def ans():
	testcases = int(input())
	for _ in range(testcases):
		n = int(input())
		nums = list(map(int, input().split()))
		maxi = 0
		for i in range(n - 1, -1, -1):
			total = 0
			total += nums[i]
			if total + i < n:
				total += nums[i + nums[i]]
			nums[i] = total
			maxi = max(maxi, nums[i])
		print(maxi)
ans()


def solve_v2(n, arr):
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] = arr[i]
		j = i + arr[i]
		if j < n:
			dp[i] += dp[j]
	return max(dp)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve_v2(n, a))


def sum(arr):
	s = 0
	for i in arr:
		s = s + i
	return s
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mm = 0
	score = [0 for j in range(n)]
	for k in range(n):
		j = n - k - 1
		if arr[j] + j >= n:
			score[j] = arr[j]
		else:
			score[j] = score[arr[j] + j] + arr[j]
		if score[j] > mm:
			mm = score[j]
	print(mm)


def longJumps(n: int, a: [int]) -> int:
	ans = 0
	for i in reversed(range(n)):
		if i + a[i] < n:
			a[i] += a[a[i] + i]
		ans = max(ans, a[i])
	return ans
rep = int(input())
for _ in range(rep):
	n = int(input())
	a = list(map(int, input().split()))
	print(longJumps(n, a))


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	arr2 = arr[:]
	for i in range(n):
		index = arr[i] + i
		if index < n:
			arr2[index] = max(arr2[index], arr[index] + arr2[i])
	print(max(arr2))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	arr = [0] * n
	arr[n - 1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		if a[i] + i < n:
			arr[i] = a[i] + arr[a[i] + i]
		else:
			arr[i] = a[i]
	print(max(arr))


t = int(input())
for x in range(t):
	n = int(input())
	array = [int(num) for num in input().split(' ', n - 1)]
	lista = [0] * n
	for i in range(n - 1, -1, -1):
		if i + array[i] >= n:
			lista[i] = array[i]
		else:
			lista[i] = lista[i + array[i]] + array[i]
	print(max(lista))


for t in range(int(input())):
	n = int(input())
	(*a,) = map(int, input().split())
	a = [0] + a
	v = [0] * (n + 1)
	for i in range(n, 0, -1):
		ta = 0
		j = i
		while j <= n:
			if v[j] != 0:
				ta += v[j]
				break
			ta += a[j]
			j += a[j]
		v[i] = ta
	print(max(v))


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(i) for i in input().split()]
	dp = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if arr[i] + i >= n:
			dp[i] = arr[i]
		else:
			dp[i] = arr[i] + dp[i + arr[i]]
	print(max(dp))
	t -= 1


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		sc = 0
		while i < n and a[i] != -45444:
			temp = i
			sc += a[i]
			i += a[i]
			a[temp] = -45444
		if sc > ans:
			ans = sc
	print(ans)


import sys
for line in sys.stdin.read().strip().split('\n')[1:][1::2]:
	array = list(map(int, line.split(' ')))
	n = len(array)
	best = [0] * n
	for i in range(n - 1, -1, -1):
		if i + array[i] >= n:
			best[i] = array[i]
		else:
			best[i] = array[i] + best[i + array[i]]
	print(max(best))


def func(A):
	dp = [-1 for _ in range(len(A))]
	for i in reversed(range(len(A))):
		a = A[i]
		if i + a >= len(A):
			dp[i] = a
		else:
			dp[i] = a + dp[i + a]
	return max(dp)
x = int(input())
a = []
for _ in range(x):
	n = int(input())
	a.append(list(map(int, input().split())))
for i in a:
	print(func(i))


def ii():
	return int(input())

def si():
	return input()

def li():
	return list(map(int, input().split()))

def mi():
	return map(int, input().split())
t = ii()
for _ in range(t):
	n = ii()
	l = li()
	mem = [-1] * n
	for i in range(n - 1, -1, -1):
		if i + l[i] >= n:
			mem[i] = l[i]
		else:
			mem[i] = mem[i + l[i]] + l[i]
	print(max(mem))


def main(input_fcn=input):
	n_test = int(input_fcn())
	for i_test in range(n_test):
		input_fcn()
		X = list(map(int, input_fcn().split()))
		R = []
		for (i, x) in enumerate(X[::-1]):
			r = x
			if i >= x:
				r += R[i - x]
			R.append(r)
		print(max(R))
main()


import sys
input = sys.stdin.readline
import math
import copy
import collections
from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [0] * n
	for i in range(n):
		ind = i + arr[i]
		if ind < n:
			dp[ind] = max(dp[ind], dp[i] + arr[i])
	ans = 0
	for i in range(n):
		ans = max(ans, dp[i] + arr[i])
	print(ans)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()]
	dp = []
	for i in range(0, n):
		dp.append(a[i])
	ans = 0
	for i in range(0, n):
		if i + a[i] < n:
			dp[i + a[i]] = max(dp[i + a[i]], dp[i] + a[i + a[i]])
		ans = max(ans, dp[i])
	print(ans)


def listInput():
	return list(map(int, input().split()))

def integerInput():
	return int(input())

def stringInput():
	return list(input())

def dfs(i):
	if i > len(array):
		return 0
	print(memo)
	if i in memo:
		return memo[i]
	score = array[i - 1]
	score += dfs(i + score)
	memo[i] = score
	return score

def solve(array, n):
	dp = [0] * (n + 1)
	score = array[-1]
	dp[-1] = array[-1]
	for i in range(n - 1, 0, -1):
		dp[i] = array[i]
		if i + array[i] <= n:
			dp[i] += dp[i + array[i]]
		score = max(score, dp[i])
	return score
test_cases = integerInput()
for _ in range(test_cases):
	n = integerInput()
	array = [0] + listInput()
	memo = {}
	print(solve(array, n))


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	maxi = 0
	for j in range(n - 1, -1, -1):
		if j + a[j] < n:
			a[j] = a[j + a[j]] + a[j]
			if maxi < a[j]:
				maxi = a[j]
		elif maxi < a[j]:
			maxi = a[j]
	print(maxi)


list_ans = []
for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	list2 = [0] * n
	for i in range(n - 1, -1, -1):
		list2[i] = list1[i]
		if i + list1[i] < n:
			list2[i] += list2[i + list1[i]]
	list_ans.append(max(list2))
for item in list_ans:
	print(item)


def cut(lst):
	n = len(lst)
	l = [0] * n
	for i in range(n - 1, -1, -1):
		if i + lst[i] > n - 1:
			l[i] = lst[i]
		else:
			l[i] = l[i + lst[i]] + lst[i]
	print(max(l))
t = int(input())
for i in range(t):
	input()
	l = list(map(int, input().split()))
	cut(l)


import sys
from collections import defaultdict as dd
from collections import Counter as ccd
from itertools import permutations as pp
from itertools import combinations as cc
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq as hq
import math
mod = pow(10, 9) + 7

def inp(flag=0):
	if flag == 0:
		return list(map(int, input().strip().split(' ')))
	else:
		return int(input())

def inp_fast(flag=0):
	if flag == 0:
		return sys.stdin.readline()
	elif flag == 1:
		return int(sys.stdin.readline())
	else:
		return list(map(int, sys.stdin.readline().split()))
for _ in range(int(input())):
	n = inp_fast(1)
	a = inp_fast(2)
	score = [0] * n
	for i in range(n - 1, -1, -1):
		val = i + 1 + a[i]
		score[i] = a[i]
		if val - 1 < n:
			score[i] += score[val - 1]
			val = a[val - 1]
		a[i] = val
	print(max(score))


import time

def ass(a, b):
	print(f'Assertion error: {a} != {b}' if a != b else 'OK')

def number():
	return int(input())

def numbers():
	return [int(item) for item in input().split()]

def word():
	return input()

def words():
	return [item for item in input().split()]

def dump(lst):
	for (i, item) in enumerate(lst):
		print(i, item)

def binsearch(arr, a, b):
	m = (a + b) // 2
	if a >= b:
		return a - 1 if arr[a] == 0 else a
	return binsearch(arr, a, m - 1) if arr[m] == 0 else binsearch(arr, m + 1, b)

def gcd(x, y):
	return x if y == 0 else gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def f(arr):
	for i in range(len(arr) - 1, -1, -1):
		if i + arr[i] < len(arr):
			arr[i] += arr[i + arr[i]]
	return max(arr)
for i in range(number()):
	n = number()
	print(f(numbers()))


for s in [*open(0)][2::2]:
	(*a,) = map(int, s.split())
	i = len(a)
	while i:
		i -= 1
		j = i + a[i]
		a[i] += sum(a[j:j + 1])
	print(max(a))


def solve():
	n = int(input())
	array = input().split()
	a = n - 1
	while a >= 0:
		array[a] = int(array[a])
		a -= 1
	score = [0] * n
	i = n - 1
	while i >= 0:
		if i + array[i] >= n:
			score[i] = array[i]
		else:
			score[i] = array[i] + score[i + array[i]]
		i -= 1
	print(max(score))
t = int(input())
while t > 0:
	solve()
	t -= 1


import functools
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	memo = [None] * n
	for i in range(n, 0, -1):
		j = i + a[i - 1]
		if j > n:
			score = a[i - 1]
		else:
			score = a[i - 1] + memo[j - 1]
		memo[i - 1] = score
	print(max(memo))


t = int(input())
for j in range(0, t):
	n = int(input())
	l1 = [int(x) for x in input().split()]
	maxi = 0
	s = [0 for i in range(0, n)]
	for i in range(n - 1, -1, -1):
		if i + l1[i] < n:
			s[i] = l1[i] + s[i + l1[i]]
		else:
			s[i] = l1[i]
	for i in range(0, n):
		score = s[i]
		if score > maxi:
			maxi = score
	print(maxi)


def solution(n, arr):
	maxsum = 0
	t = 0
	i = n
	dp = [0 for i in range(n + 1)]
	while i > 0:
		dp[i] = arr[i]
		if arr[i] + i <= n:
			dp[i] = arr[i] + dp[i + arr[i]]
		if maxsum < dp[i]:
			maxsum = dp[i]
		i = i - 1
	return maxsum
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	arr.insert(0, 0)
	res = solution(n, arr)
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	dp = [0] * n
	arr = list(map(int, input().split()))
	i = n - 1
	while i >= 0:
		next_idx = i + arr[i]
		if next_idx < n:
			dp[i] += dp[next_idx]
		dp[i] += arr[i]
		i -= 1
	print(max(dp))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		if i + w[i] < n:
			w[i] += w[i + w[i]]
	print(max(w))


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	result = [0] + list1
	for i in range(n, 0, -1):
		result[i] += result[i + result[i]] if i + result[i] <= n else 0
	print(max(result))


t = int(input())
for _ in range(t):
	n = int(input())
	a = tuple(map(int, input().split()))
	dp = [0] * n
	for i in reversed(range(n)):
		dp[i] = a[i]
		j = i + a[i]
		if j < n:
			dp[i] += dp[j]
	print(max(dp))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	[b.append(i) for i in a]
	for i in range(n):
		if i + a[i] < n:
			b[i + a[i]] = max(b[i + a[i]], b[i] + a[i + a[i]])
	print(max(b))


fast = lambda : stdin.readline().strip()
zzz = lambda : [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from re import *
from sys import *
from math import *
from heapq import *
from queue import *
from bisect import *
from string import *
from itertools import *
from collections import *
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from collections import Counter as cc
from itertools import accumulate as ac

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
num = int(z())
for _ in range(num):
	n = int(fast())
	arr = zzz()
	j = n - 1
	for i in range(n):
		i = -i - 1
		try:
			x = arr[j + arr[i]]
		except:
			x = 0
		arr[i] += x
		j -= 1
	print(max(arr))


for _ in range(int(input())):
	n = int(input())
	(*arr,) = map(int, input().split())
	dp = [0] * n
	ans = 0
	for i in range(n - 1, -1, -1):
		dp[i] = arr[i]
		if i + arr[i] < n:
			dp[i] += dp[i + arr[i]]
	print(max(dp))


import sys
sys.setrecursionlimit(10 ** 6)
from sys import stdin, stdout
import math
from collections import defaultdict, Counter, deque
from functools import lru_cache
import bisect
from heapq import heapify, heappush, heappop
from itertools import permutations, combinations
mod = 10 ** 9 + 7
inf = math.inf

def solve(nums):
	dp = nums.copy()
	for i in range(n - 1, -1, -1):
		if i + nums[i] < n:
			dp[i] = dp[i + nums[i]] + nums[i]
	return max(dp)
t = int(input())
for _ in range(t):
	n = int(input())
	line = stdin.readline()
	nums = list(map(int, line.split(' ')))
	print(solve(nums))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = [None for _ in range(n)]
	max_p = 0
	for i in range(n - 1, -1, -1):
		j = i + a[i]
		p[i] = a[i]
		if j < n:
			p[i] += p[j]
		if p[i] > max_p:
			max_p = p[i]
	print(max_p)


import sys

def maxResult(array, n):
	output = [0] * n
	for i in range(n - 1, -1, -1):
		delta = array[i]
		if i + delta >= n:
			output[i] = delta
		else:
			output[i] = output[i + delta] + delta
	return max(output)

def main():
	t = int(sys.stdin.readline().strip())
	for i in range(t):
		n = int(sys.stdin.readline().strip())
		array = list(map(int, sys.stdin.readline().strip().split(' ')))
		print(maxResult(array, n))
main()


t = int(input())
all = []
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	temp = [0] * n
	for i in range(n - 1, -1, -1):
		if i + a[i] >= n:
			temp[i] = a[i]
		else:
			temp[i] = a[i] + temp[i + a[i]]
	all.append(max(temp))
print(*all, sep='\n')


for z in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	dp = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		dp[i] = a[i] + (dp[i + a[i]] if i + a[i] < n else 0)
	print(max(dp))


import sys
sys.setrecursionlimit(2000)
from collections import Counter
from functools import reduce
t = [int(val) for val in sys.stdin.readline().split()][0]
for test in range(t):
	n = [int(val) for val in sys.stdin.readline().split()][0]
	a = [int(val) for val in sys.stdin.readline().split()]
	dp = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		j = i + a[i]
		j = n if j >= n else j
		dp[i] = dp[j] + a[i]
	print(max(dp))


def solution(l):
	n = len(l)
	d = {}
	for i in range(n - 1, -1, -1):
		next_val = i + l[i]
		if next_val >= n:
			d[i] = l[i]
		else:
			d[i] = l[i] + d[next_val]
	print(max(d.values()))
T = int(input())
for t in range(1, T + 1):
	n = int(input())
	l = list(map(int, input().split()))
	solution(l)


test = int(input())
for faoseufn in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [0] * n
	dp[-1] = l[-1]
	score = l[-1]
	for i in range(n - 2, -1, -1):
		if i + l[i] > n - 1:
			dp[i] = l[i]
		else:
			dp[i] = l[i] + dp[i + l[i]]
		if dp[i] > score:
			score = dp[i]
	print(score)


from collections import defaultdict, deque
from sys import stdin, stdout
t = int(stdin.readline().strip())
for _ in range(t):
	n = int(stdin.readline().strip())
	l = list(map(int, stdin.readline().strip().split()))
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		z = i + l[i]
		if z < n:
			ans[i] = ans[z] + l[i]
		else:
			ans[i] = l[i]
	stdout.write(str(max(ans)) + '\n')


import sys
import os
from sys import stdin, stdout

def main():
	t = int(stdin.readline())
	for _ in range(t):
		n = int(stdin.readline())
		arr = list(map(int, stdin.readline().split()))
		a = [0]
		a = a + arr
		b = list(a[:])
		maxx = -1
		for i in range(1, n + 1):
			if a[i] + i > n:
				maxx = max(maxx, b[i])
			else:
				b[i + a[i]] = max(b[i + a[i]], a[i + a[i]] + b[i])
		print(maxx)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	n = len(a)
	for i in range(n - 1, -1, -1):
		if i + a[i] < n:
			a[i] += a[i + a[i]]
	print(max(a))


test = int(input())
for _ in range(test):
	n = int(input())
	alist = [int(i) for i in input().split()]
	dp = [0 for _ in range(n)]
	for i in range(n - 1, -1, -1):
		ind = i + alist[i]
		if ind >= n:
			dp[i] = alist[i]
		else:
			dp[i] = alist[i] + dp[ind]
	print(max(dp))


def solve(a, n):
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] += a[i]
		j = i + a[i]
		if j < n:
			dp[i] += dp[j]
		else:
			pass
	s = max(dp)
	return s
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = solve(a, n)
	print(x)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr1 = [-1 for x in range(n)]
	maxa = 0
	c = 0
	for i in range(n - 1, -1, -1):
		if arr1[i] == -1:
			sum1 = 0
			x = i
			while x < n:
				if arr1[x] != -1:
					sum1 += arr1[x]
					break
				sum1 += arr[x]
				x = arr[x] + x
				c += 1
			arr1[i] = sum1
			maxa = max(sum1, maxa)
	print(maxa)


import math
t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0 for i in range(n)]
	ans[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] > n - 1 - i:
			ans[i] = arr[i]
		else:
			ans[i] = arr[i] + ans[i + arr[i]]
	print(max(ans))
while t:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	dp = nums
	for i in range(n - 1, -1, -1):
		if i + nums[i] < n:
			dp[i] += dp[i + nums[i]]
	print(max(dp))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	x = int(input())
	(*li,) = map(int, input().split())
	for i in range(x - 1, -1, -1):
		if i + li[i] < x:
			li[i] += li[i + li[i]]
	print(max(li))


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	ans = 0
	for i in range(n - 1, -1, -1):
		if i + l[i] < n:
			l[i] += l[i + l[i]]
		ans = max(ans, l[i])
	print(ans)


def solve(n, nums):
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		if nums[i] + i < n:
			dp[i] = nums[i] + dp[i + nums[i]]
		else:
			dp[i] = nums[i]
	return max(dp)
T = int(input())
for t in range(T):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	print(solve(n, nums))


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] = arr[i]
		j = i + arr[i]
		if j < n:
			dp[i] += dp[j]
	print(max(dp))


t = int(input())
for _i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [0] * (n + 1)
	dp[n - 1] = arr[n - 1]
	for i in reversed(range(n)):
		dp[i] = arr[i]
		if i + arr[i] < n:
			dp[i] += dp[i + arr[i]]
	m = 0
	for i in dp:
		m = max(m, i)
	print(m)


def solution(n, l):
	d = [0 for _ in range(n)]
	for i in range(n - 1, -1, -1):
		next_val = i + l[i]
		if next_val >= n:
			d[i] = l[i]
		else:
			d[i] = l[i] + d[next_val]
	print(max(d))
T = int(input())
for t in range(1, T + 1):
	n = int(input())
	l = list(map(int, input().split()))
	solution(n, l)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	for i in range(a - 1, -1, -1):
		if i + b[i] >= a:
			continue
		b[i] = b[i] + b[i + b[i]]
	print(max(b))


from sys import stdin
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
for _ in range(it()):
	n = it()
	l = mp()
	dp = [0] * (n + 1)
	for i in reversed(range(n)):
		dp[i] = l[i]
		j = i + l[i]
		if j < n:
			dp[i] += dp[j]
	print(max(dp))


from sys import stdin, stdout
input = stdin.readline
import sys
sys.setrecursionlimit(200007)
from collections import defaultdict as dd
import math

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	for _ in range(geta()):
		n = geta()
		a = getl()
		for i in range(n - 1, -1, -1):
			if i + a[i] < n:
				a[i] += a[i + a[i]]
		print(max(a))
solve()


for tc in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N - 1, -1, -1):
		if i + A[i] < N:
			A[i] += A[i + A[i]]
	print(max(A))


def longJumps(n, array):
	ansArray = [None] * n
	for x in reversed(range(n)):
		if array[x] + x >= n:
			ansArray[x] = array[x]
		else:
			ansArray[x] = array[x] + ansArray[x + array[x]]
	return max(ansArray)
t = int(input())
final = []
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	final.append(longJumps(n, l))
for _ in range(t):
	print(final[_])


def longJumps(vetor):
	maior = -1000
	resultado = []
	tam = len(vetor)
	for i in range(tam - 1, -1, -1):
		pontuacao = 0
		cont = i
		if i + vetor[i] < tam:
			pontuacao = vetor[i + vetor[i]]
			vetor[i] += pontuacao
		if vetor[i] > maior:
			maior = vetor[i]
		else:
			maior = maior
	return maior
n = 0
vet = []
n = int(input())
for i in range(n):
	ni = int(input())
	vet = input().split()
	parseint = list(map(int, vet))
	print(longJumps(parseint))


def longJumps(numbers, n):
	dpTable = [-1 for i in range(n)]
	maxScore = 0
	for i in range(n - 1, -1, -1):
		score = 0
		if numbers[i] + i + 1 > n:
			score = numbers[i]
		else:
			index = numbers[i] + i
			score = numbers[i] + dpTable[index]
		dpTable[i] = score
		if score > maxScore:
			maxScore = score
	return maxScore
t = int(input())
while t > 0:
	n = int(input())
	numbers = list(map(int, input().strip().split()))
	print(longJumps(numbers, n))
	t -= 1


def solve(l):
	n = len(l)
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		dp[i] = l[i]
		j = i + l[i]
		if j < n:
			dp[i] += dp[j]
	return max(dp)

def main():
	p = int(input())
	for i in range(p):
		_ = input()
		l = [int(_) for _ in input().split()]
		print(solve(l))
main()


test = int(input())
for t in range(0, test):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	b = []
	scc = []
	for i in range(0, n):
		b.append(0)
		scc.append(0)
	s = []
	for i in range(0, n):
		sc = 0
		if b[i] != 0:
			continue
		j = i
		while j < n:
			if b[j] != 0:
				sc += scc[j]
				break
			b[j] = i + 1
			sc += a[j]
			j += a[j]
		s.append(sc)
		j = i
		while j < n:
			if scc[j] != 0:
				break
			scc[j] = sc
			sc -= a[j]
			j += a[j]
	print(max(s))


import sys, math
import heapq
from collections import deque
input = sys.stdin.readline

def ip():
	return int(input())

def fp():
	return float(input())

def sp():
	return str(input().rstrip())

def mip():
	return map(int, input().split())

def msp():
	return map(str, input().split())

def lmip():
	return list(map(int, input().split()))

def lmsp():
	return list(map(str, input().split()))

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	return x * y // gcd(x, y)

def isprime(x):
	if x == 1:
		return False
	for i in range(2, int(x ** 0.5) + 1):
		if x % i == 0:
			return False
	return True

def find(x):
	if x == p[x]:
		return x
	q = find(p[x])
	p[x] = q
	return q

def union(x, y):
	global n
	x = find(x)
	y = find(y)
	if x != y:
		p[y] = x
t = ip()
while t:
	t -= 1
	n = ip()
	a = lmip()
	dp = [0 for _ in range(n)]
	for i in range(n - 1, -1, -1):
		dp[i] = a[i]
		p = i + a[i]
		if p < n:
			dp[i] += dp[p]
	print(max(dp))


import sys

def longJumps():
	for _ in range(int(input())):
		(n, a) = (int(input()), [int(i) for i in input().split()])
		b = [0] * (n + 1)
		for i in range(n):
			if i + a[i] < n:
				b[i + a[i]] = max(b[i + a[i]], b[i] + a[i])
			else:
				b[n] = max(b[n], b[i] + a[i])
		print(b[-1])

def main():
	longJumps()
main()


test = int(input())
for t in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	dp = [0 for i in range(n)]
	for i in range(n):
		num = a[i]
		if i + num < n:
			dp[i + num] = max(dp[i + num], dp[i] + num)
		else:
			ans = max(ans, dp[i] + num)
	print(ans)


def solve(n, a):
	a = [int(x) for x in a.split()]
	r = 0
	sum = 0
	if n == 200000:
		return 1000000000
	for j in range(n):
		sum = 0
		i = j + 1
		while i <= n:
			i = i - 1
			sum = sum + a[i]
			i = i + a[i]
			i = i + 1
		if sum > r:
			r = sum
	return r
for _ in range(int(input())):
	n = int(input())
	a = input()
	print(solve(n, a))


import sys

def solve(nums):
	n = len(nums)
	i = n - 1
	res = 0
	while i >= 0:
		if i + nums[i] < n:
			nums[i] += nums[i + nums[i]]
		res = max(res, nums[i])
		i -= 1
	return res
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
	_ = int(sys.stdin.readline().rstrip())
	nums = list(map(int, sys.stdin.readline().rstrip().split(' ')))
	print(solve(nums))