C. Cirno and Operationstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputCirno 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.InputThe 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$$$.OutputFor each test case, print an integer representing the maximum possible sum.ExampleInput51-100025 -321000 199 7 9 -9 9 -8 7 -8 911678 201 340 444 453 922 128 987 127 752 0Output-1000
8
1001
2056
269891
NoteIn 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$$$.