Alex正在参加BrMeast另一个视频的拍摄,BrMeast让Alex准备25万吨TNT,但Alex听不太清,就准备了$$$n$$$个箱子,排成一排等待卡车。左边第 $$$i$$$ 个盒子重 $$$a_i$$$ 吨。
Alex 将使用的所有卡车都装有相同数量的箱子,用 $$$k$$$ 表示。加载按以下方式进行:
- 第一个 $$$k$$$ 盒子被送到第一辆卡车,
- 第二个 $$$k$$$ 箱子被运往第二辆卡车,
- $$$\dotsb$$$
- 最后 $$$k$$$ 箱子被送到第 $$$\frac{n}{k}$$$ 卡车。
装载完成后,每辆卡车必须恰好装有 $$$k$$$ 个箱子。换句话说,如果在某个时刻不可能将 $$$k$$$ 箱子准确地装载到卡车上,那么使用该 $$$k$$$ 的装载选项是不可能的。
Alex 讨厌正义,因此他希望两辆卡车的总重量之间的最大绝对差值尽可能大。如果只有一辆卡车,则该值为 $$$0$$$。
Alex 有相当多的人脉,因此对于每 $$$1 \leq k \leq n$$$,他可以找到一家公司,使其每辆卡车都能恰好容纳 $$$k$$$ 箱子。打印任意两辆卡车总重量之间的最大绝对差。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案。
示例
输入 #1
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
1 9 0 189114 112141
注意
在第一种情况下,我们应该选择两辆卡车,因此第一辆卡车只有第一个箱子,第二辆卡车只有第二个箱子。
在第二种情况下,我们应该选择六辆卡车,因此最大值为 $$$10$$$,最小值为 $$$1$$$,答案为 $$$10 - 1 = 9$$$。
在第三种情况下,对于任何可能的$$$k$$$,卡车将具有相同的箱子总重量,因此答案是$$$0$$$。