给定一个长度为 $n$ 的整数数组 $a$。

你可以执行以下操作：选择一个区间 $[l, r]$（$1 \le l \le r \le n$），并将元素 $a_l, a_{l+1}, \dots, a_r$ 的值替换为 $(l + r)$。

你的任务是计算在最多执行一次上述操作的情况下，数组总和的最大可能值。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 2n$）。

输入的额外约束：所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数 —— 如果你最多可以执行一次上述操作，数组元素总和的最大可能值。

Samples

4
3
2 5 1
2
4 4
4
1 3 2 1
5
3 2 0 9 10

13
8
20
32

注意

在第一个例子中，你可以对子数组 $[3, 3]$ 执行操作，得到数组 $[2, 5, 6]$，其和为 $13$。

在第二个例子中，你无需执行任何操作。

在第三个例子中，你可以对子数组 $[1, 4]$ 执行操作，得到数组 $[5, 5, 5, 5]$，其和为 $20$。

在第四个例子中，你可以对子数组 $[2, 3]$ 执行操作，得到数组 $[3, 5, 5, 9, 10]$，其和为 $32$。