D. Asem Hates Valentine (Yellow)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Being single is not an option anymore – it is the destiny I am facing. In two days, it is Valentine's Day. Everyone is thinking about gifts for their partners… and here I am writing this problem.

I will show that I am not sad. I am happy. I am good. I am glad to be single. Why would I need commitments?

Anyway…

You are given an array $$$a$$$ of $$$n$$$ integers.

You may perform the following operation at most once:

Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$), and swap $$$a_i$$$ and $$$a_j$$$.

Your task is to determine the maximum possible sum of the array after performing at most one such operation.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

For each test case:

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — we forgot the case when $$$n = 1$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n(1 \le a_i \le 10^4)$$$ .

Output

For each test case, print a single integer – the maximum possible sum of the array after performing at most one swap.

Example
Input
1
3
4 1 2
Output
7