题目描述

翁老师给了你一个由 $n$ 个正整数组成的序列 $a$。

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

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

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

三角形判定条件：设边长为 $a$、$b$、$c$，则必须满足 $a + b > c$、$a + c > b$ 且 $b + c > a$。

输入格式

本题有多组数据

第一行输入一个整数 $t$，代表测试数据组数。

• 接下来每一组第一行输入一个整数 $n$。
• 接下来一行输入 $n$ 个空格隔开的整数分别代表 $a_1,a_2,\cdots,a_n$。

输出格式

对于每一组数据，在单独一行中输出最终剩余元素的可能最大值。

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

10
1593
11
39

提示

样例 1 解释

• 在第一组数据中，序列已经只有一个元素。最终剩余元素的值为 $10$。

• 在第二组数据中，初始序列为 $[998, 244, 353]$。以下操作序列是合法的：

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

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

数据范围

对于 $100\%$ 的数据，$1 \le t \le 10^4$，$1\leq n\leq 2\cdot 10^5$，$1\leq a_i\leq 1000$，保证所有数据 $n$ 的总和不超过 $2\cdot 10^5$。

• 子任务 1（30 分）：保证 $n\leq 2$
• 子任务 2（30 分）：保证 $\sum n\leq 2000$
• 子任务 3（40 分）：没有特殊限制。