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. 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). For each test case, print an integer representing the maximum possible sum. 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\to8). 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).