有 $$$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)$$$ 的数量。
示例
输入 #1
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
输出 #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)$$$。