Hizitizi's Array Cutting

Hizitizi is a new character in our story. In every episode, he gets a task to do from his imaginary girlfriend (He made her on his mind). Today's task is to cut an array. As, she is imaginary, Hizitizi can do some cheating with her. He is now telling you to complete this task for him, so that he can spend all the day with his imaginary girlfriend.

You will be given an array of positive integer of n length. You have to split this array in three part so that.

1. Every part is non-empty.
2. If we take two index i and j (j > i), and

Suppose we have an array [1, 2, 3, 1, 2]. Now, we can split this array in 3 part [1, 2], [3], [1, 2], where sum of these three part is respectively 3, 3 and 3. Now, (3 - 3)2 + (3 - 3)2 = 0, which is minimum.

Input

Input will contain T (1 ≤ T ≤ 100) test cases.
Each case will contain two lines of input. First line will contain n (3 ≤ n ≤ 105), length of the array.
Next line will contain n integer (a1, a2 ... an), where (1 ≤ ai ≤ 104).

Note: Sum of n over all test cases won't be more than 106.

Output

Print the minimum value of (A - B)2 + (B - C)2.

Sample

Input	Output
1 5 1 2 3 1 2	0