A. Алиса и книги
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы есть $$$n$$$ книг. $$$1$$$-я книга содержит $$$a_1$$$ страниц, $$$2$$$-я книга содержит $$$a_2$$$ страниц, $$$\ldots$$$, $$$n$$$-я книга содержит $$$a_n$$$ страниц. Алиса делает следующее:

  • Она разделяет все книги на две непустые стопки. Таким образом, каждая книга оказывается ровно в одной из двух стопок.
  • Алиса читает в каждой стопке одну книгу с наибольшим номером.

Алиса очень любит читать. Помогите ей найти, какое максимальное суммарное количество страниц она сможет прочитать, разделив книги на две стопки.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество книг у Алисы.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — количество страниц в каждой книге.

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

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

Пример
Входные данные
5
2
1 1
4
2 3 3 1
5
2 2 3 2 2
2
10 3
3
1 2 3
Выходные данные
2
4
5
13
5
Примечание

В первом наборе входных данных Алиса может положить в первую стопку книгу с номером $$$1$$$, а во вторую стопку книгу с номером $$$2$$$. Тогда она прочитает $$$a_1 + a_2 = 1 + 1 = 2$$$ страницы.

Во втором наборе входных данных Алиса может положить книги с номерами $$$2$$$ и $$$3$$$ в первую стопку, а книги с номерами $$$1$$$ и $$$4$$$ во вторую стопку. Тогда из первой стопки она прочитает книгу с наибольшим номером $$$3$$$, а из второй стопки книгу с наибольшим номером $$$4$$$. Тогда она прочитает $$$a_3 + a_4 = 3 + 1 = 4$$$ страницы.