著名的江河有很多：长江、黄河、还有黑龙江等等。

小w想探究江河的奥秘，他发现河岸有 $n$ 个石头堆起来的石堆，每个石堆有 $a_i$ 个石头。不过他认为这些石碓高度不一很不美观，因此他想把这些石碓的高度变得尽量统一。对于任意两个石碓 $i$ 和 $j$，他可以进行操作：从石碓 $i$ 中拿出 $1$ 个石头，放到石碓 $j$ 中。

小w想知道所有操作完成之后，最高的石碓和最低的石碓的高度差是多少。即求：$\max_{1 \leq i \leq n} a_i - \min_{1 \leq i \leq n} a_i$ 的最小值。

第一行一个整数 $t$，表示有 $t$ 组数据。

每组数据第一行一个整数 $n$，表示有 $n$ 个石碓。

每组数据第二行 $n$ 个整数 $a_i$，表示每个石碓的高度。

每组数据输出一行一个整数，表示所有操作完成之后，最高的石碓和最低的石碓的高度差的最小值。

样例解释

对于第一组数据，所有石碓的高度已经相同，因此最高和最低的高度差为 $0$。

对于第二组数据，小w可以进行一次操作，将石碓 $1$ 中的 $1$ 个石头放到石碓 $3$ 中，这样所有石碓的高度都为 $2$，因此最高和最低的高度差为 $0$。

对于第三组数据，小w可以下面操作:

• 从 $3$ 号石碓中拿出 $1$ 个石头放到 $1$ 号石碓中，此时石碓变为: $[2, 2, 2, 1, 5]$
• 从 $5$ 号石碓中拿出 $1$ 个石头放到 $3$ 号石碓中，此时石碓变为: $[2, 2, 2, 2, 4]$
• 从 $5$ 号石碓中拿出 $1$ 个石头放到 $4$ 号石碓中，此时石碓变为: $[2, 2, 2, 3, 3]$

此时最高和最低的高度差为 $1$。

数据范围

对于 $50\%$ 的数据，$n \leq 10$。

对于 $100\%$ 的数据，$1 \leq t \leq 10^4$，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9, \sum_{i=1}^{t} n \leq 10^6$。