Each galaxy 'i' in the universe is assigned a unique position in the universe given by A(i), for the ith galaxy. It is known that the distance between 2 galaxies is given as Dist (i,j) = ( |i^2 - j^2| + |A(i)^2 - A(j)^2| ).

The events are held in a host galaxy, and every other galaxy has to travel to that galaxy to participate. For this, of course, the organizers have to pay the galaxy for their transportation, lodging and daily expenses. The organizers wonder, what could be the maximum transportation expenses that they have to pay?

Help them by finding MAX(Dist (i,j)).

Input

First line contains a single integer T, denoting the number of Test Cases.

Each Test Case contains 2 lines. 1st line containing a single number ’n’ denoting the number of galaxies (numbered 1 to n).

2nd line contains ’n’ space separated integers signifying A(i) for 1<=i<=n.

Warning: Fast IO may be needed in some languages.

Output

T lines, each containing an Integer, the answer to the corresponding test case.

Constraints

1 <= T <= 10

2 <= n <= 10^5

1 <= A(i) <= 10^9

Example

Input:
1
2
4 3

Output:
10

Explanation

Dist(i,j) is maximum for i=1, j=2.