Two Options

题号：NC314212
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 小苯可以进行以下操作任意次（可以不操作）：选择一个下标 $i\left(1 \leqq i \leqq n\right)$ ，将 $a_i$ 增加 $1$ 。在这次操作中，他还可以额外选择至多一个下标 $j\left(1 \leqq j \leqq n;\ j \neq i\right)$ ，将 $a_j$ 减少 $1$ 。

$\hspace{15pt}$ 换句话说，每次操作可以从以下两种形式中任选一种进行：
$\hspace{23pt}\bullet$ 形式一：只选择一个下标 $i$ ，执行 $a_i \leftarrow a_i + 1$
$\hspace{23pt}\bullet$ 形式二：选择两个不同的下标 $i$ 和 $j$ ，执行 $a_i \leftarrow a_i + 1$ 和 $a_j \leftarrow a_j - 1$
$\hspace{15pt}$ 所有操作中， $a_i$ 的值可以为负数。

$\hspace{15pt}$ 小苯希望通过若干次操作，使得数组中所有元素的值都相等。你的任务就是求出所需的最少操作次数。
$\hspace{15pt}$ 可以证明，在上述规则下，总能通过有限次操作使所有元素相等。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示数组的长度。
第二行输入  个整数 ，表示数组中的元素。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示最少操作次数。

示例1

输入

复制

输出

复制

1
1
0

说明

对于第一组测试数据，选择  执行一次形式一的操作即可。