Read problem statements in [Mandarin], [Vietnamese], and [Russian] as well.

For a given array $B_{1}, B_{2}, \ldots, B_{M}$ of length at least 3, let's define its weight as the largest value of $(B_{i}-B_{j})\cdot(B_{j}-B_{k})$ over all possible triples (i, j, k) with 1 ≤ i, j, k ≤ M and $i \neq j, j \neq k, k \neq i$.

You are given $a sorted array A_{1}, A_{2}, \ldots, A_{N} ($that is, A_{1} ≤ A_{2} ≤ $\ldots$ ≤ A_{N}).

Calculate the sum of weights of all contiguous subarrays of A of length at least 3. That is, count the sum of weights of arrays $[A_{i}, A_{i+1}, \ldots, A_{j}]$ over all 1 ≤ i < j ≤ N with j-i≥ 2.

------ Input Format ------

• The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$.

------ Output Format ------

For each test case, print a single line containing the sum of weights of all subarrays of A of length at least 3.

------ Constraints ------

$1 ≤T ≤1000$
$3 ≤N ≤3000$
$1 ≤A_{1} ≤A_{2} \ldots ≤A_{N} ≤10^{6}$.
- Sum of $N$ over all test cases won't exceed $6000$.

----- Sample Input 1 ------
2
4
1 2 3 4
5
1 42 69 228 2021
----- Sample Output 1 ------
4
1041808

----- explanation 1 ------
Explanation of the first test case of the sample:

Given array has $3$ subarrays of length at least $3$.

$[1, 2, 3]$ has weight $1$, with $i = 1, j = 2, k = 3$: $(1-2)\cdot(2-3) = 1$
$[2, 3, 4]$ has weight $1$, with $i = 3, j = 2, k = 1$: $(4-3)\cdot(3-2) = 1$
$[1, 2, 3, 4]$ has weight $2$, with $i = 1, j = 2, k = 4$: $(1-2)\cdot(2-4) = 2$, or with $i = 1, j = 3, k = 4$: $(1-3)\cdot(3-4) = 2$

见题面

见题面