问题描述

给定初始一个数组 $a$，其长度为 $n$。你可以依次执行以下步骤：

• 选择一个位置 $i$，满足 $1\le i\le |a|$ 且 $a_i=|a|+1-i$，其中 $|a|$ 表示数组 $a$ 的长度。
• 在数组 $a$ 的末尾追加 $i-1$ 个 $0$。

在任意次操作后，数组 $a$ 的长度最大可能为多少？

输入格式

第一行输入一个正整数 $t$，表示测试数据的组数。$(1\le t\le 1000)$

对于每组测试数据：

第一行输入一个正整数 $n$，表示数组 $a$ 的初始长度。$(1\le n\le 3\times 10^5)$

第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示数组 $a$ 的初始元素。$(1\le a_i\le 10^{12})$

数据保证所有 $n$ 之和在 $3\times 10^5$ 以内。

输出格式

对于每组测试数据，输出一行一个整数，表示数组 $a$ 的最大长度。

样例输入

4
5
2 4 6 2 5
5
5 4 4 5 1
4
6 8 2 3
1
1

样例输出

10
11
10
1

说明

在第一个测试案例中，我们可以先选择 $i = 4$ ，因为 $a_4 = 5 + 1 - 4 = 2$ 。之后，数组变为 $[2, 4, 6, 2, 5, 0, 0, 0]$ 。然后，我们可以选择 $i = 3$ ，因为 $a_3 = 8 + 1 - 3 = 6$ 。之后，数组变为 $[2, 4, 6, 2, 5, 0, 0, 0, 0, 0]$ ，长度为 $10$ 。由此可以看出，任何操作序列都不会使最终数组变长。

在第二个测试案例中，我们可以先选择 $i=2$ ，然后选择 $i=3$ ，最后选择 $i=4$ 。最后得到的数组为 $[5, 4, 4, 5, 1, 0, 0, 0, 0, 0, 0]$ ，长度为 $11$ 。