A. 爱丽丝与书

每次测试时间限制：$1$ 秒 每次测试内存限制：$256$ 兆字节

爱丽丝有 $n$ 本书。第 $1$ 本书有 $a_1$ 页，第 $2$ 本书有 $a_2$ 页，……，第 $n$ 本书有 $a_n$ 页。爱丽丝执行如下操作：

她将所有书分成两堆非空的书堆，每本书恰好属于其中一堆。 爱丽丝阅读每一堆中编号最大的那一本书。

爱丽丝非常喜欢阅读，请你帮她求出：将书分成两堆后，她能阅读的最大总页数。

输入

每组测试包含多个测试用例。 第一行输入一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。

每个测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示书的数量。

每个测试用例的第二行输入 $n$ 个整数 $a_1,a_2,\dots,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$ 页。