C. Длинные прыжки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

  • Выбери число $$$i$$$ ($$$1 \leq i \leq n$$$) — стартовую позицию в массиве. Помести фишку на позицию $$$i$$$ (на элемент $$$a_i$$$);
  • Пока $$$i \leq n$$$, прибавь к своему результату значение $$$a_i$$$ и переместись на $$$a_i$$$ вправо (т.е. замени $$$i$$$ на $$$i + a_i$$$);
  • Если $$$i > n$$$, то Поликарп заканчивает игру.

Например, если $$$n = 5$$$ и $$$a = [7, 3, 1, 2, 3]$$$, тогда следующие варианты игр возможны:

  • Поликарп выбирает $$$i = 1$$$. Процесс игры: $$$i = 1 \overset{+7}{\longrightarrow} 8$$$. Результат игры: $$$a_1 = 7$$$.
  • Поликарп выбирает $$$i = 2$$$. Процесс игры: $$$i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$$$. Результат игры: $$$a_2 + a_5 = 6$$$.
  • Поликарп выбирает $$$i = 3$$$. Процесс игры: $$$i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$$$. Результат игры: $$$a_3 + a_4 = 3$$$.
  • Поликарп выбирает $$$i = 4$$$. Процесс игры: $$$i = 4 \overset{+2}{\longrightarrow} 6$$$. Результат игры: $$$a_4 = 2$$$.
  • Поликарп выбирает $$$i = 5$$$. Процесс игры: $$$i = 5 \overset{+3}{\longrightarrow} 8$$$. Результат игры: $$$a_5 = 3$$$.

Помогите Поликарпу узнать, какой максимальный результат он может получить, если он выбирает стартовую позицию оптимально.

Входные данные

В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массива $$$a$$$.

В следующей строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

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

Пример
Входные данные
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
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных максимальный результат достигается при выборе $$$i = 1$$$.

В третьем наборе входных данных максимальный результат достигается при выборе $$$i = 2$$$.

В четвёртом наборе входных данных максимальный результат достигается при выборе $$$i = 1$$$.