You are given an integer array a of length n.
You can perform the following operation: choose a range [l, r] (1 ≤ l ≤ r ≤ n) and replace the value of elements a_l, a_l+1, …, a_r with (l + r).
Your task is to calculate the maximum possible total array sum if you can perform the aforementioned operation at most once.
Input
The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.The first line of each test case contains a single integer n (1 ≤ n ≤ 2 · 10^5).The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 2n).Additional constraint on the input: the sum of n over all test cases doesn't exceed 2 · 10^5.
Output
For each test case, print a single integer — the maximum possible total array sum if you can perform the aforementioned operation at most once.
Examples
Note
In the first example, you can perform the operation on the subarray [3, 3], resulting in the array [2, 5, 6] and the sum 13.In the second example, you don't need to perform any operation.In the third example, you can perform the operation on the subarray [1, 4], resulting in the array [5, 5, 5, 5] and the sum 20.In the fourth example, you can perform the operation on the subarray [2, 3], resulting in the array [3, 5, 5, 9, 10] and the sum 32.