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$$$.

Input

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$$$.

Output

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

Note

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)$$$.

Game on Axis

Examples