Description

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 100$) — the number of books Alice has.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the number of pages in each book.

Output

For each test case, output a single integer — the maximum number of pages Alice can read.

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

Note

In the first test case, Alice can put book number $1$ in the first pile, and book number $2$ in the second pile. Then she will read $a_1 + a_2 = 1 + 1 = 2$ pages.

In the second test case, Alice can put books with numbers $2$ and $3$ in the first pile, and books with numbers $1$ and $4$ in the second pile. Then she will read the book with the highest number $3$ from the first pile, and the book with the highest number $4$ from the second pile. Then she will read $a_3 + a_4 = 3 + 1 = 4$ pages.