You are given an array $A = [A_{1}, A_{2}, \ldots, A_{N}]$ of length N.

You can right rotate it any number of times (possibly, zero). What is the maximum value of A_{1} + A_{N} you can get?

Note: Right rotating the array $[A_{1}, A_{2}, \ldots, A_{N}]$ once gives the array $[A_{N}, A_{1}, A_{2}, \ldots, A_{N-1}]$. For example, right rotating [1, 2, 3] once gives [3, 1, 2], and right rotating it again gives [2, 3, 1].

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases. The description of the test cases follows.
• The first line of each test case contains a single integer N, denoting the length of array A.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$ — denoting the array A.

------ Output Format ------

For each test case, output on a new line the maximum value of A_{1}+A_{N} you can get after several right rotations.

------ Constraints ------

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ across all test cases does not exceed $10^{5}$

----- Sample Input 1 ------
3
2
5 8
3
5 10 15
4
4 4 4 4

----- Sample Output 1 ------
13
25
8

----- explanation 1 ------
Test case $1$: Whether you right rotate the array or not, you will always end up with $A_{1}+A_{N} = 13$.

Test case $2$: It is optimal to right rotate the array once after which the array becomes $[15,5,10]$ with $A_{1} + A_{N} = 25$.

Test case $3$: No matter how much you right rotate the array, you will always obtain $A_{1} + A_{N} = 8$.

见题面

见题面