Description

地上有 $n$ 个桶，第 $i$ 个桶中有 $a_i$ 颗石子。每次你可以进行以下两种操作之一：

• 从任意一个非空的桶中取出一颗石子。
• 将一颗石子从一个（必须非空）桶移到任意另一个桶（可以是空桶）。

你最少需要操作多少次，才能使所有桶中的石子数相等？

Input Format

有多组测试数据。输入的第一行为一个整数 $T$，表示测试用例的数量。每组测试数据包括两行：

第一行为一个整数 $n$（$1 \le n \le 10^5$），表示桶的数量。

第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$），表示每个桶中的石子数。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

Output Format

对于每个测试用例，输出一行一个整数，表示使所有桶中石子数相等所需的最少操作次数。

4
3
1 1 0
4
2 2 2 2
3
0 1 4
1
1000000000

2
0
3
0

Hint

对于第一个样例，可以将前两个桶的石子全部取出。

对于第二个样例，每个桶中本就有相同数量的石子，无需操作。

对于第三个样例，可以先从第 3 个桶中移走 1 颗石子放到第 1 个桶，然后再从第 3 个桶中取出 2 颗石子。

由 ChatGPT 5 翻译