Canvas Painting

在去年的成功之后，Samuel W. E. R. Craft 的名声持续增长，现在他有资金投入各种他想到的项目。他最新的想法是创作一系列画布，要求画布上的颜色图案不能有重复的颜色。

Samuel 购买了一套不同尺寸的白色画布。由于手工绘制太耗时，他设计了一台大型机器来自动化绘画过程。

绘画过程如下：

1. 将所有画布按某种选定的顺序排列在机器的传送带上。
2. 选择一种颜色 $C$ 和一个数字 $F$（$F$ 应小于颜色为 $C$ 的画布数量）。
3. 从左到右，所有颜色为 $C$ 的画布都会被重新绘制。前 $F$ 个颜色为 $C$ 的画布被涂上一种新颜色 $X$，其余颜色为 $C$ 的画布被涂上另一种新颜色 $Y$。颜色 $X$ 和 $Y$ 由机器选择，它们彼此不同，且与之前使用过的任何颜色都不同。此步骤中消耗的墨水量等于被重新绘制的画布尺寸之和。
4. 重复步骤 2 和 3，直到所有画布的颜色都各不相同。

例如，假设 Samuel 购买了四块尺寸分别为 3, 5, 5 和 7 的画布。下图展示了两种不同的绘画方案。

任务

给定 Samuel 购买的画布尺寸，你能否帮助他计算出为了使所有画布颜色各不相同，机器所需消耗的最小墨水量？

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例由两行组成。第一行包含一个整数 $N$，表示画布的数量。下一行包含 $N$ 个空格分隔的整数，表示画布的尺寸。

数据范围

$1 \le T \le 100$ 测试用例数量。 $1 \le N_i \le 100\,000$ 第 $i$ 个测试用例中画布的数量。 $1 \le s \le 100\,000$ 每块画布的尺寸。 $1 \le \sum_{i=1}^{T} N_i \le 100\,000$ 单个测试文件中所有测试用例的画布总数。

输出格式

输出包含 $T$ 行，每行对应一个测试用例：为了使所有画布颜色各不相同，机器所需消耗的最小墨水量。

样例

样例输入 1

2
3
7 4 7
4
5 3 7 5

样例输出 1

29
40