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.

Note

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$.