A7757.捞薯条

Yuilice老家的码头里面下薯条雨了，Yuilice开心的去码头捞了整整$n(1 \leq n \leq 10^5)$箱的薯条，并且准备叫$\frac{n}{k}$辆卡车来运回家。

每辆卡车共会运输$k(1 \leq k \leq n)$箱薯条，例:

• 第一辆卡车会运输前$k$箱薯条
• 第二辆卡车会运输第$k+1$ ~ $2 · k$箱薯条
• ....
• 第$\frac{n}{k}$辆卡车运输末尾$k$箱薯条

每一辆卡车必须装载$k$箱薯条，否则就无法回程，现在Yuilice需要去考虑运输给出的运费该如何计算，于是他决定运费由这些卡车当中载重最重的卡车与载重最轻的卡车之间重量的差值决定的，差值多少，那么给出的运费就多少。

注意:如果只有一辆卡车，那么差值则为0

现在,Yuilice需要知道,他最多给出的运费为多少呢？

输入第一行为一个正整数$t(1 \leq t \leq 10^4)$，代表接下来会有$t$组样例。

随后每组样例的第一行，输入一个正整数$n(1 \leq n \leq 10^5)$，代表共有$n$箱薯条。

随后一行，输入$n$个正整数$a_i(1 \leq a_i \leq 10^9)$代表每箱薯条的重量。

输出一个整数，代表Yuilice需要支付的最多运费。

Note

在于第一组样例当中，$k=1$，最重的卡车重量为$9$，最轻的卡车重量为$1$，答案则为$9 - 1 = 8$。