你被要求观察你的侄子,他喜欢以一种奇怪的方式玩积木。
他有 $$$n$$$ 个盒子,第 $$$i$$$ 个盒子有 $$$a_i$$$ 块。他的游戏包括两个步骤:
1.他选择任意一个框$$$i$$$;
2. 他尝试将所有块从第 $$$i$$$ 个盒子移动到其他盒子。
你不想让你的侄子伤心,所以你决定在一些盒子里多放几个方块,这样无论他选择哪个盒子$$$i$$$都不会伤心。您需要放置的最少额外块数是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 盒子的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) - 每个框中的块数。
保证测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您需要放置的最小块数。可以证明答案总是存在的,即。 e.块的数量是有限的。
示例
输入 #1
3 3 3 2 2 4 2 2 3 2 3 0 3 0
输出 #1
1 0 3
注意
在第一个测试用例中,例如,您可以将一个额外的块放入第一个框中,并使 $$$a = [4, 2, 2]$$$。如果您的侄子选择了带有 $$$4$$$ 块的盒子,那么我们将把两个块移动到第二个盒子,将两个块移动到第三个盒子。如果他选择带有 $$$2$$$ 块的盒子,那么他会将这两个块移动到另一个带有 $$$2$$$ 块的盒子。
在第二个测试用例中,您不需要放置任何额外的块,因为无论您的侄子选择哪个盒子,他总是可以使其他盒子相等。
在第三个测试用例中,您应该放置 $$$3$$$ 额外的块。例如,您可以将 $$$2$$$ 块放入第一个框中,将 $$$1$$$ 块放入第三个框中。你会得到数组 $$$a = [2, 3, 1]$$$。