题目描述
亚历克斯正在参与拍摄布尔马斯特的另一个视频，布尔马斯特让亚历克斯准备25万吨TNT炸药，但亚历克斯没有听清楚，于是他准备了 $n$ 个箱子，并把它们摆成一排等待卡车。左边的 $i$ 个箱子重 $a_i$ 吨。
亚历克斯要使用的所有卡车都装有相同数量的箱子，用 $k$ 表示。装载过程如下：
- 第一个 $k$ 个箱子装到第一辆卡车上、
- 第二个 $k$个 箱子装到第二辆卡车上、
- $\dotsb$
- 最后 $k$ 个箱子装到 第$\frac{n}{k}$ 辆卡车上。
装载完成后，所有箱子都被装到卡车上，并且每辆卡车上必须都有 $k$ 个箱子。换句话说，如果在某一时刻无法将 $k$ 个箱子准确地装入卡车，那么 $k$ 个箱子的装载选项就无法实现。
亚历克斯讨厌公正，所以他希望两辆卡车总重量的最大绝对值差越大越好。如果只有一辆卡车，这个值就是 $0$ 。
亚历克斯有很多关系，所以他总都能找到一家公司，使其每辆卡车正好能装载 $k$ 个箱子（他能找到任意数量的卡车， $1 \leq k \leq n$ ）。打印任意两辆卡车总重量的最大绝对差值。
注意：请用scanf读入，cin会超时
输入
第一行包含一个整数 $t$ ( $1 \leq t \leq 10^4$ ) - 测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 150\,000$ ) - 箱子数量。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \leq a_i \leq 10^9$ ) - 箱子的权重。
保证所有测试用例的 $n$ 之和不超过 $150\,000$ 。
5
2
1 2
6
10 2 3 6 1 3
4
1000000000 1000000000 1000000000 1000000000
15
60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294
8
19957 69913 37531 96991 57838 21008 14207 19198
提示
在第一个样例中，找两辆卡车时，两辆车上的箱子重量分别为1，2，绝对值差为1 ；找两辆卡车时为0。所以绝对值差最大为1。
在第二个样例中，找六辆卡车时，差值最大为9，没有比这更优的方案。
在第三个样例中，无论找几辆卡车都为0。
在第四个样例中，找三辆卡车时，绝对值差最大。
在第五个样例中，找四辆卡车时，绝对值差最大。