CF1787D.Game on Axis

There are $n$ points $1,2,\ldots,n$, each point $i$ has a number $a_i$ on it. You're playing a game on them. Initially, you are at point $1$. When you are at point $i$, take following steps:

• If $1\le i\le n$, go to $i+a_i$,
• Otherwise, the game ends.

Before the game begins, you can choose two integers $x$ and $y$ satisfying $1\le x\le n$, $-n \le y \le n$ and replace $a_x$ with $y$ (set $a_x := y$). Find the number of distinct pairs $(x,y)$ such that the game that you start after making the change ends in a finite number of steps.

Notice that you do not have to satisfy $a_x\not=y$.

有 $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 \ne y$。

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 10^4)$ — the number of test cases.

The first line of each test case contains one integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of points.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-n \le a_i \le n$) — the numbers on the axis.

It's guaranteed that the sum of $n$ does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print a line containing a single integer — the number of distinct pairs $(x,y)$ with which the game ends.

对于每个测试用例，输出一行，包含一个整数——游戏结束时不同的数对 $(x,y)$ 的数量。

In the first test case, the pairs $(x,y)$ with which the game ends are $(1,-1)$ and $(1,1)$, corresponding to the routes $1\rightarrow 0$ and $1\rightarrow 2$. Note that $(1,2)$ is invalid since when $n=1$, $y=2$ violates $-n\le y\le n$. $(1,0)$ is also invalid since you will go from $1$ to $1$ forever.

In the second test case, the pairs are $(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$.

In the fourth test case, the pairs are $(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)$.

在第一个测试用例中，游戏结束时的数对 $(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)$。