Problem Description

小沃沃所在的世界是一个二维平面。他有 $n$ 个朋友，第 $i$ 个朋友距离他的距离为 $a[i]$，小沃沃并不知道这些朋友具体在什么点上。

请问在最优情况下，小沃沃的朋友两两之间的欧几里得距离的和的最小值是几？

假设小沃沃的位置为 $P_0 = (x_0,y_0)$，第 $i$ 个朋友的位置为 $P_i = (x_i,y_i)$，对于所有的 $i$，需要满足 $dist(P_0, P_i) = a[i]$，并且$\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{dist(P_i,P_j)}}$ 最小，其中 $dist(X,Y)$ 为连接点 $X$ 和点 $Y$ 的线段的长度。$x_i,y_i$ 都可以是任意实数。

Input

第一行一个正整数 $test(1 \leq test \leq 10)$ 表示数据组数。

对于每组数据，第一行一个正整数 $n(1 \leq n \leq 100000)$。

接下来一行 $n$ 个整数，第 $i$ 个整数 $a[i](1 \leq a[i] \leq 1000000000)$ 表示第 $i$ 个朋友和小沃沃的距离。

Output

对每组数据输出一行一个数，表示 $\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{dist(P_i,P_j)}}$ 的最小值。答案需要四舍五入到整数。

2
2
3 5
5
1 2 3 4 5

2
20