题目描述

超级士兵们给了你一个由 $n$ 个正整数组成的序列 $a$。

你必须重复执行以下操作直到序列中只剩下 $1$ 个元素：

• 选择两个不同的下标 $i$ 和 $j$
• 选择一个正整数 $x$，使得存在一个非退化三角形$^{\text{∗}}$，其边长为 $a_i$、$a_j$ 和 $x$
• 删除这两个元素 $a_i$ 和 $a_j$，并将 $x$ 追加到序列 $a$ 的末尾

请找出最终序列中唯一剩余元素可能的最大值。

$^{\text{∗}}$当边长为 $a$、$b$、$c$ 的三角形满足 $a + b > c$、$a + c > b$ 且 $b + c > a$ 时，该三角形是非退化的。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 1000$）——序列 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，在单独一行中输出最终剩余元素的可能最大值。

输入输出样例 #1

输入 #1

4
1
10
3
998 244 353
5
1 2 3 4 5
9
9 9 8 2 4 4 3 5 3

输出 #1

10
1593
11
39

说明/提示

在第一个测试用例中，序列已经只有一个元素。最终剩余元素的值为 $10$。

在第二个测试用例中，初始序列为 $[998, 244, 353]$。以下操作序列是合法的：

1. 删除 $a_2 = 244$ 和 $a_3 = 353$，并追加 $596$ 到序列末尾。此时 $a$ 变为 $[998, 596]$
2. 删除 $a_1 = 998$ 和 $a_2 = 596$，并追加 $1593$ 到序列末尾。此时 $a$ 变为 $[1593]$

可以证明最终元素不可能超过 $1593$。因此答案为 $1593$。