题目描述

为了杀死祂，你收集了 $n$ 个珍贵材料，每个材料具有特定的强度 $a_i$。你需要选择一部分材料，并按照强度从小到大的顺序依次加入初始药水中，以配置出最强大的毒药。配置过程中，药水的强度会根据特殊规则更新，你的目标是使最终药水强度尽可能大。

初始药水强度为 $0$ 。每次添加材料 $a_i$​ 时，强度更新规则如下：

• 设添加前的当前强度为 $S$;

• 设上一次添加的药水强度为 $a_j$ (若是第一次添加，则 $a_j=0$);

• 新强度通过某种特殊反应生成：$S_{new}=S+(a_i-2\cdot a_j)^2$;

请计算你能配置出的最大最终强度。

输入格式

每个测试文件包含多组测试数据。第一行包含测试数据的组数 $T$ ($1≤T≤10^3$）。每组测试数据的格式如下。

每组测试数据的第一行包含一个整数 $n$ ($1≤n≤10^5$)，表示珍贵材料的数量。

第二行包含 $n$ 个整数 $a_0 ,\ a_1 ,\ a_2 \ ...,\ a_{n-1}$ ($1≤a_i\le 10^{5}$)，代表每个材料的强度。

在每个测试文件内，保证所有测试数据的 $n$ 之和不超过 $10^6$ 。

输出格式

对于每组数据，输出一行一个整数，表示能配置出的最大最终强度。

2
5
1 2 3 4 5
5
2 2 2 2 2

25
20