CF1452B.Toy Blocks

You are asked to watch your nephew who likes to play with toy blocks in a strange way.

He has $n$ boxes and the $i$-th box has $a_i$ blocks. His game consists of two steps:

1. he chooses an arbitrary box $i$;
2. he tries to move all blocks from the $i$-th box to other boxes.

If he can make the same number of blocks in each of $n - 1$ other boxes then he will be happy, otherwise, will be sad. Note that your nephew can only move the blocks from the chosen box to the other boxes; he cannot move blocks from the other boxes.

You don't want to make your nephew sad, so you decided to put several extra blocks into some boxes in such a way that no matter which box $i$ he chooses he won't be sad. What is the minimum number of extra blocks you need to put?

你需要照看你的侄子，而他喜欢以一种奇怪的方式玩积木。

他有 $n$ 个盒子，其中第 $i$ 个盒子中有 $a_i$ 块积木。他的游戏包含两个步骤：

1. 他任意选择一个盒子 $i$；
2. 他尝试将第 $i$ 个盒子中的所有积木全部移到其余的盒子中。

如果他能使得其余 $n - 1$ 个盒子中每个盒子的积木数量都相等，那么他会很开心；否则，他会难过。注意：你的侄子只能将所选盒子中的积木移出到其他盒子中，而不能从其他盒子中移动积木。

你不想让你的侄子难过，因此你决定向某些盒子中添加若干额外的积木，使得无论他选择哪一个盒子 $i$，他都不会难过。请问：你需要添加的最少积木数量是多少？

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains the integer $n$ ($2 \le n \le 10^5$) — the number of boxes.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the number of blocks in each box.

It's guaranteed that the sum of $n$ over test cases doesn't exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, print a single integer — the minimum number of blocks you need to put. It can be proved that the answer always exists, i. e. the number of blocks is finite.

对于每个测试用例，输出一个整数——你需要放置的方块的最小数量。可以证明答案一定存在，即方块数量是有限的。

In the first test case, you can, for example, put one extra block into the first box and make $a = [4, 2, 2]$. If your nephew chooses the box with $4$ blocks, then we will move two blocks to the second box and two blocks to the third box. If he chooses the box with $2$ blocks then he will move these two blocks to the other box with $2$ blocks.

In the second test case, you don't need to put any extra blocks, since no matter which box your nephew chooses, he can always make other boxes equal.

In the third test case, you should put $3$ extra blocks. For example, you can put $2$ blocks in the first box and $1$ block in the third box. You'll get array $a = [2, 3, 1]$.

在第一个测试用例中，例如，你可以在第一个盒子中额外放入一个方块，使得 $a = [4, 2, 2]$。如果你的侄子选择了含有 $4$ 个方块的盒子，那么我们将把其中的两个方块移至第二个盒子、另外两个方块移至第三个盒子；如果他选择了含有 $2$ 个方块的盒子，则他会将这两个方块全部移至另一个同样含有 $2$ 个方块的盒子。

在第二个测试用例中，你无需额外放入任何方块，因为无论你的侄子选择哪一个盒子，他总能使其余盒子中的方块数量相等。

在第三个测试用例中，你应该放入 $3$ 个额外的方块。例如，你可以在第一个盒子中放入 $2$ 个方块，在第三个盒子中放入 $1$ 个方块，从而得到数组 $a = [2, 3, 1]$。