丹尼尔正在观看一支足球队在训练期间进行的比赛。他们希望在那次训练中提高他们的传球技巧。
游戏涉及 $$$n$$$ 名玩家,相互进行多次传球。不幸的是,由于球移动得太快,比赛结束后丹尼尔无法知道比赛中涉及了多少个球。他唯一知道的是每个球员在整个训练过程中传球的次数。
求游戏中涉及的最小可能球数。
输入
输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — 测试用例的数量。接下来是测试用例描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 玩家数量。
测试用例的第二行包含整数序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 玩家传递的传球数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入 #1
4 4 2 3 3 2 3 1 5 2 2 0 0 4 1000000000 1000000000 1000000000 1000000000
输出 #1
1 2 0 1
注意
在第一个测试用例中,只有一个球,游戏可以这样进行:
$$$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$$$。
在第二个测试用例中,不可能只用一个球来玩游戏。用两个球玩的一种可能的方式:
$$$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$。
$$$2 \右箭头 3 \右箭头 2 \右箭头 1$$$
在第三个示例中,没有传球,因此 $$$0$$$ 球是可能的。