题目描述

本题中，对于一个有限集 \(S\)，使用 \(|S|\) 表示 \(S\) 的元素个数。

yummy 在某编程比赛使用了一个广为人知的算法把集合 \(S\) 变成 \(S\cup T\)：

• 如果 \(|S| < |T|\)，那么交换 \(S, T\)。
• 依次将 \(T\) 中的每个元素插入集合 \(S\) 中。

这个做法被称为“启发式合并”。然而 yummy 在这场比赛中，把第一步的条件写反了，导致一直 TLE 找不到原因，浪费了很多比赛时间。后来，队友就把这个条件写反了的算法称为“玉米式合并”。

不难看出，把 \(S, T\) 两个集合进行玉米式合并时，需要进行 \(\max(|S|, |T|)\) 次元素插入。

现有 \(n\) 个集合 \(S_1, \ldots, S_n\)，满足 \(\forall 1 \le i \le n, |S_i| = a_i\)，且任意两个集合的交为空。现在 yummy 需要进行 \(n-1\) 次操作，每次选择两个未被丢弃的集合 \(S_i, S_j\)，把 \(S_i\) 通过玉米式合并变成 \(S_i\cup S_j\)，然后丢弃 \(S_j\)。你需要计算，在最坏（元素插入次数最多）的方案下，yummy 一共进行了多少次元素插入。

输入格式

本题有多组测试数据。输入的第一行有一个正整数 \(T\) （\(1 \le T \le 10^5\)），表示数据组数。

对于每组测试数据，输入两行：

其中第一行为一个正整数 \(n\) （\(1 \le n \le 10^5\)），表示集合的个数。

第二行为 \(n\) 个正整数 \(a_1, \ldots, a_n\) （\(1 \le a_i \le 2 \times 10^9\)），表示集合 \(S_i\) 的大小。

保证所有测试点的 \(n\) 之和不超过 \(5 \times 10^5\)。

输出格式

对于每组测试数据，输出一行一个自然数，表示答案。

样例输入

2
3
1 10 100
1
5

样例输出

210
0