题目背景

小智 正在参与拍摄另一部 小程 的视频。小程 要求 小智 准备 25万吨 TNT，但 小智 没听清，于是他准备了 $n$个箱子，并把它们按顺序排成一排等待装车。从左到右第 $i$ 个箱子的重量为$a_i$ 吨。

题目描述

小智 使用的所有卡车每辆都装相同数量的箱子，记为 $k$。装车规则如下：第$1$ 到第 $k$ 个箱子装到第一辆卡车，第 $k+1$ 到第 $2k$个箱子装到第二辆卡车，依此类推，最后 $k$ 个箱子装到第 $n/k$辆卡车。装车完成后，每辆卡车必须恰好装 $k$ 个箱子。如果在某一步无法凑齐$k$ 个箱子，则这种 $k$ 的装车方式不可行。换句话说，只有当 $k$是$n$的因数时，这种装车方式才是合法的。

小智非常讨厌"公平"，因此他希望两辆卡车所装箱子总重量的绝对差尽可能大。如果只有一辆卡车，这个值为 $0$。小智 人脉很广，因此对于所有 $1 \le k \le n$，他都能找到能装恰好 $k$个箱子的卡车公司。请你求出任意两辆卡车的总重量最大绝对差。

输入格式

第一行包含一个整数 $t \ (1 \le t \le 10^4)$，表示测试用例数量。对于每个测试用例，第一行包含一个整数 $n \ (1 \le n \le 150000)$表示箱子的数量。第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，其中 $1 \le a_i \le 10^9$ 表示每个箱子的重量。保证所有测试用例的 $n$之和不超过 $150000$。

输出格式

对于每个测试用例，输出一个整数，表示答案。

输入样例

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
9
0
189114
112141

样例说明

样例 1：选择 $k=1$，每辆卡车装 $1$ 个箱子，第一辆卡车重量为 $1$，第二辆卡车重量为 $2$，最大差值为 $|2-1|=1$。

样例 2：选择 $k=1$，共有 $6$ 辆卡车，最大重量为 $10$，最小为 $1$，因此答案为 $10-1=9$。

样例 3：无论选择哪个合法的 $k$，每辆卡车的总重量都相同，因此答案为 $0$。

50% 数据 $t=1 ,\; n<=500$