Game on Axis

Description:

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.

Sample Input:

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

Sample Output:

2
8
6
7
20
17
34
30
40

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