Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/B

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/B

Repovive

Rayan has $n$ artifacts with power levels $a_1, a_2, \ldots, a_n$ .

The resonance of an arrangement is the sum of absolute differences between adjacent elements:

$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$

Rayan can reverse exactly one contiguous segment, or leave the arrangement unchanged. Find the maximum possible resonance.

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 100$ ).

Each test case consists of:

The first line contains $n$ ( $1 \le n \le 1000$ ), the number of artifacts.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $|a_i| \le 10^9$ ).

The sum of $n$ over all test cases does not exceed $5000$ .

Output

For each test case, print the maximum possible resonance.

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\begin{array}{l} R_1 \\ R_2 \\ \vdots \\ R_t \end{array}

2B. Resonance

Input

Output

Input

Output

Samples

Input

Output