C. Чирно и операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Чирно есть последовательность $$$a$$$ длины $$$n$$$. Она может выполнять каждую из следующих операций любое количество раз (возможно, ноль). Есть дополнительное условие — перед операцией текущая длина $$$a$$$ не должна быть равна $$$1$$$:

  • Развернуть последовательность. Формально, $$$[a_1,a_2,\ldots,a_n]$$$ становится $$$[a_n,a_{n-1},\ldots,a_1]$$$ после операции.
  • Заменить последовательность на её разностную последовательность. Формально, $$$[a_1,a_2,\ldots,a_n]$$$ становится $$$[a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}]$$$ после операции.

Найдите максимальную возможную сумму элементов $$$a$$$ после операций.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 50$$$) — длина последовательности $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i|\le 1000$$$) — последовательность $$$a$$$.

Выходные данные

Для каждого набора входных данных выведите целое число, представляющее максимальную возможную сумму.

Пример
Входные данные
5
1
-1000
2
5 -3
2
1000 1
9
9 7 9 -9 9 -8 7 -8 9
11
678 201 340 444 453 922 128 987 127 752 0
Выходные данные
-1000
8
1001
2056
269891
Примечание

В первом наборе входных данных Чирно не может выполнить ни одной операции, поэтому ответ равен $$$-1000$$$.

Во втором наборе входных данных Чирно сначала разворачивает последовательность, затем заменяет последовательность на её разностную последовательность: $$$[5,-3]\to[-3,5]\to[8]$$$. Можно доказать, что это максимизирует сумму, поэтому ответ равен $$$8$$$.

В третьем наборе входных данных Чирно может не выполнять операции, поэтому ответ равен $$$1001$$$.