B. The Third Sidetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe pink soldiers have given you a sequence $$$a$$$ consisting of $$$n$$$ positive integers.You must repeatedly perform the following operation until there is only $$$1$$$ element left. Choose two distinct indices $$$i$$$ and $$$j$$$. Then, choose a positive integer value $$$x$$$ such that there exists a non-degenerate triangle$$$^{\text{∗}}$$$ with side lengths $$$a_i$$$, $$$a_j$$$, and $$$x$$$. Finally, remove two elements $$$a_i$$$ and $$$a_j$$$, and append $$$x$$$ to the end of $$$a$$$. Please find the maximum possible value of the only last element in the sequence $$$a$$$.$$$^{\text{∗}}$$$A triangle with side lengths $$$a$$$, $$$b$$$, $$$c$$$ is non-degenerate when $$$a+b > c$$$, $$$a+c > b$$$, $$$b+c > a$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 1000$$$) — the elements of the sequence $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor each test case, output the maximum possible value of the only last element on a separate line.ExampleInput41103998 244 35351 2 3 4 599 9 8 2 4 4 3 5 3Output10
1593
11
39
NoteOn the first test case, there is already only one element. The value of the only last element is $$$10$$$.On the second test case, $$$a$$$ is initially $$$[998,244,353]$$$. The following series of operations is valid: Erase $$$a_2=244$$$ and $$$a_3=353$$$, and append $$$596$$$ to the end of $$$a$$$. $$$a$$$ is now $$$[998,596]$$$. Erase $$$a_1=998$$$ and $$$a_2=596$$$, and append $$$1593$$$ to the end of $$$a$$$. $$$a$$$ is now $$$[1593]$$$. It can be shown that the only last element cannot be greater than $$$1593$$$. Therefore, the answer is $$$1593$$$.