You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[云岭茶马] 普洱茶饼的压制

题目背景

在云南西双版纳的古茶山上，茶农们正忙着准备通过“茶马古道”运送普洱茶。为了方便长途运输并利于陈化，茶农需要将散落在茶坊里的 $n$ 块小茶砖压制成一块巨大的“万寿金瓜”大茶饼。

题目描述

现在茶坊里有 $n$ 块原始茶砖，每块茶砖的质量分别为 $a_1, a_2, \dots, a_n$（单位：两）。

压制过程遵循古老的传统，每次只能将两块茶砖合并。具体规则如下：

1. 从当前茶坊中任选两块茶砖，设它们的质量分别为 $x$ 和 $y$。
2. 将这两块茶砖放入压制机。由于压制过程中会有少许茶叶破碎变成细粉（损耗），合并后得到的新茶砖质量为：$x + y - 1$。
3. 重复上述步骤，直到茶坊里只剩下 一块 巨大的茶饼。

茶农斯博想知道，他按照什么样的顺序压制这些茶砖，最后剩下的那一块大茶饼的质量最大是多少？

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示初始茶砖的数量。
• 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每块茶砖的质量。

输出格式

对于每组测试数据，输出一个整数，表示最后剩下的那块大茶饼的质量。

输入输出样例

样例输入 #1

2
3
2 3 4
5
1 1 1 1 1

样例输出 #1

7
1

数据范围

• $1 \le T \le 100$
• $1 \le n \le 10^5$
• $1 \le a_i \le 10^9$
• 保证所有测试点的 $n$ 之和不超过 $2 \times 10^5$。