给定一个数组 $x_1, x_2, \dots, x_n$。

创建一个包含 $n$ 个顶点的无向图，初始时图中没有边。

随后，对于每一对满足 $u < v$ 的顶点 $(u, v)$，在图中添加一条连接顶点 $u$ 和 $v$ 的边，其权重为 $x_v - x_u$。

你的目标是求出该图中最小生成树的权重。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 300\,000$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示给定数组中整数的个数。

每个测试用例的下一行包含 $n$ 个用空格分隔的整数 $x_1, x_2, \dots, x_n$ ($-300\,000 \le x_i \le 300\,000$)，表示给定的数组。

保证所有测试用例中 $n$ 的总和不超过 $300\,000$。

输出格式

对于每个测试用例，输出一个整数：描述图中最小生成树的权重。

样例

样例输入 1

2
5
1 2 3 4 5
3
10 45 10

样例输出 1

4
-35