题目描述

操场上有\(N\)堆石子排成一排，每次Kiana可以选择两堆相邻的石子进行合并，并在原地得到一堆新的石子，直到所有的石子都被合并为一堆。

Kiana的石子自然是与众不同的，具体而言，初始时每堆石子都有一个奇妙值，这个值可能是任意整数。在合并两堆石子后，得到的新石子堆的奇妙值为两堆石子的奇妙值之差。由于两个正整数作差不满足交换律，因此Kiana可以自由决定是由哪堆石子的奇妙值减去另一堆石子的奇妙值来得到结果。

现在Kiana想知道，将操场上所有石子合并为一堆后，能得到的最大的奇妙值是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含一个正整数\(T\)，表示输入数据的组数。

接下来依次输入各组数据，每组数据第一行包含一个正整数\(N\)，表示操场上石子堆数。

每组数据第二行包含\(N\)个整数，其中第\(i\)个数\(S_i\)表示初始时第\(i\)堆石子的奇妙值。

输出格式

输出共一行，包含一个整数，表示将操场上所有石子合并为一堆后能得到的最大的奇妙值。

输入输出样例

输入样例#1：

1
3
-1 0 2 

输出样例#1：

3

输入样例#2：

stone2.in

输出样例#2：

stone2.ans

样例解释

操场上有\(3\)堆石子，其奇妙值依次为\(-1,0\)和\(2\)。

Kiana首先将第\(2\)堆和第\(3\)堆石子合并，并用第\(3\)堆石子的奇妙值减去第\(2\)堆石子的奇妙值得到新石子堆奇妙值为\(2\)。然后将新石子堆和第\(1\)堆石子合并，并用前者奇妙值减去后者奇妙值得到最终的奇妙值为\(3\)，可以证明这是奇妙值最大的方案。

数据范围

对于\(20\%\)的数据，保证\(1\leq N\leq 200\)。

对于\(40\%\)的数据，保证\(1\leq N\leq 2000\)。

对于\(70\%\)的数据，保证\(1\leq N\leq 2\times 10^5\)。

对于\(100\%\)的数据，保证\(1\leq N\leq 2\times 10^6,1\leq T\leq 5,-1000\leq S_i\leq 1000\)。