D. Игра на оси
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ точек $$$1,2,\ldots,n$$$, у каждой точки $$$i$$$ написано число $$$a_i$$$. Вы играете в игру на этих точках. Изначально вы находитесь в точке $$$1$$$. Когда вы находитесь в точке $$$i$$$, выполните следующий шаг:

  • Если $$$1\le i\le n$$$, перейдите к точке $$$i+a_i$$$;
  • В противном случае игра заканчивается.

Перед началом игры вы можете выбрать два целых числа $$$x$$$ и $$$y$$$, удовлетворяющих $$$1\le x\le n$$$, $$$-n \le y \le n$$$, и заменить число $$$a_x$$$ на $$$y$$$ (сделать $$$a_x := y$$$). Найдите количество различных пар $$$(x,y)$$$, при которых игра, которую вы начнете после замены, закончится за конечное число шагов.

Обратите внимание, что вам не нужно удовлетворять условию $$$a_x\not=y$$$.

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-n \le a_i \le n$$$) — числа на оси.

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

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

Для каждого набора входных данных выведите строку, содержащую одно целое число — количество различных пар $$$(x,y)$$$, игра с которыми конечна.

Пример
Входные данные
9
1
0
2
-1 0
2
1 -1
2
1 1
3
-1 -2 -1
3
1 -2 -1
4
-1 4 -2 1
5
1 1 1 1 -4
5
1 1 1 1 1
Выходные данные
2
8
6
7
20
17
34
30
40
Примечание

В первом наборе входных данных парами $$$(x,y)$$$, с которыми игра конечна, являются $$$(1,-1)$$$ и $$$(1,1)$$$, соответствующие маршрутам $$$1\rightarrow 0$$$ и $$$1\rightarrow 2$$$. Обратите внимание, что пара $$$(1,2)$$$ не подходит, так как при $$$n=1$$$ равенство $$$y=2$$$ нарушает $$$-n\le y\le n$$$. $$$(1,0)$$$ также не подходит, так как вы всегда переходите от $$$1$$$ к $$$1$$$, и игра не заканчивается.

Во втором наборе входных данных подходящие пары равны $$$(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$$$.

В четвертом наборе входных данных подходящие пары $$$(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)$$$.