Cirno has a sequence $a$ of length $n$. She can perform either of the following two operations for any (possibly, zero) times unless the current length of $a$ is $1$:

• Reverse the sequence. Formally, $[a_1,a_2,\ldots,a_n]$ becomes $[a_n,a_{n-1},\ldots,a_1]$ after the operation.
• Replace the sequence with its difference sequence. Formally, $[a_1,a_2,\ldots,a_n]$ becomes $[a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}]$ after the operation.

Find the maximum possible sum of elements of $a$ after all operations.

Input

The first line of input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of input test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 50$) — the length of sequence $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($|a_i|\le 1000$) — the sequence $a$.

Output

For each test case, print an integer representing the maximum possible sum.

见题面 Input 部分

见题面 Output 部分

In the first test case, Cirno can not perform any operation, so the answer is $-1000$.

In the second test case, Cirno firstly reverses the sequence, then replaces the sequence with its difference sequence: $[5,-3]\to[-3,5]\to[8]$. It can be proven that this maximizes the sum, so the answer is $8$.

In the third test case, Cirno can choose not to operate, so the answer is $1001$.