Длинные прыжки

Поликарп нашёл под ёлкой массив a из n элементов и инструкцию для игры с ним:

Выбери число i (1≤i≤n) — стартовую позицию в массиве. Помести фишку на позицию i (на элемент ai);
Пока i≤n, прибавь к своему результату значение ai и переместись на ai вправо (т.е. замени i на i+ai);
Если i>n, то Поликарп заканчивает игру.
Например, если n=5 и a=[7,3,1,2,3], тогда следующие варианты игр возможны:

Поликарп выбирает i=1. Процесс игры: i=1⟶+78. Результат игры: a1=7.
Поликарп выбирает i=2. Процесс игры: i=2⟶+35⟶+38. Результат игры: a2+a5=6.
Поликарп выбирает i=3. Процесс игры: i=3⟶+14⟶+26. Результат игры: a3+a4=3.
Поликарп выбирает i=4. Процесс игры: i=4⟶+26. Результат игры: a4=2.
Поликарп выбирает i=5. Процесс игры: i=5⟶+38. Результат игры: a5=3.
Помогите Поликарпу узнать, какой максимальный результат он может получить, если он выбирает стартовую позицию оптимально.

Входные данные
В первой строке находится одно целое число t (1≤t≤104) — количество наборов входных данных. Далее следуют t наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число n (1≤n≤2⋅105) — длина массива a.

В следующей строке находятся n целых чисел a1,a2,…,an (1≤ai≤109) — элементы массива a.

Гарантируется, что сумма n по всем наборам входных данных не превосходит 2⋅105.

Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно число — максимальный результат, который Поликарп может получить, сыграв в игру на соответствующем массиве по инструкции из условия. Обратите внимание, что Поликарп выбирает любую стартовую позицию от 1 до n таким образом, чтобы максимизировать свой результат.

0

0