该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

分糖果

Description

新春在即，小Z准备分发一些糖果给他的朋友们作为新年礼物。为了防止分给朋友的糖果不平衡，小Z决定事先处理一下分配。

现在总共有 $n$ 堆糖果（可以只有0颗糖），小Z每次可以执行以下操作的其中一种：

• 从其中任意一堆糖果中取出一颗糖自己吃掉；
• 从其中任意非空的一堆糖果中取出一颗糖放入另一堆中；

最终小Z要将 $n$ 堆糖果处理成每堆糖果的数量均相等，请问他最少需要多少次操作？

Input Format

含有多个测试用例。第一行输入一个整数 T ，代表测试用例的数量。

对于每个测试用例，第一行输入一个整数 $n$ ，表示要分的糖果堆数；

第二行输入 $n$ 个整数 $a_1, a_2, \cdots , a_n$ ，表示初始堆中糖果数量。

保证对于所有测试用例，$\sum n \le 10^6$ 。

Output Format

对于每个测试用例输出一行包含一个整数，表示最少需要的操作次数。

Input Example#1

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

Output Example#1

2
0
3
0

Data Range

$1 \le n \le 10^5, 0 \le a_i \le 10^9, \sum n \le 10^6$ 。