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

Вам дан массив $$$a$$$, изначально содержащий $$$n$$$ целых чисел. За одну операцию вы можете сделать следующее:

  • Выбрать позицию $$$i$$$ такую, что $$$1 < i \le |a|$$$ и $$$a_i = |a| + 1 - i$$$, где $$$|a|$$$ — текущая длина массива.
  • Добавить $$$i - 1$$$ нулей в конец $$$a$$$.

Какова максимально возможная длина массива $$$a$$$ после выполнения данной операции некоторое количество раз (возможно, нулевое)?

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$).

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

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

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

Пример
Входные данные
4
5
2 4 6 2 5
5
5 4 4 5 1
4
6 8 2 3
1
1
Выходные данные
10
11
10
1
Примечание

В первом наборе входных данных мы можем сначала выбрать $$$i = 4$$$, так как $$$a_4 = 5 + 1 - 4 = 2$$$. После этого массив станет равен $$$[2, 4, 6, 2, 5, 0, 0, 0]$$$. Затем мы можем выбрать $$$i = 3$$$, так как $$$a_3 = 8 + 1 - 3 = 6$$$. После этого массив станет равен $$$[2, 4, 6, 2, 5, 0, 0, 0, 0, 0]$$$, то есть будет иметь длину $$$10$$$. Можно показать, что нельзя получить более длинный массив.

Во втором наборе входных данных мы можем выбрать $$$i=2$$$, затем $$$i=3$$$, затем $$$i=4$$$. Итоговый массив будет равен $$$[5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]$$$, и его длина будет равняться $$$11$$$.