B. Toy Blocks time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output 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 ai blocks. His game consists of two steps:

he chooses an arbitrary box i; 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?

Input The first line contains a single integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains the integer n (2≤n≤105) — the number of boxes.

The second line of each test case contains n integers a1,a2,…,an (0≤ai≤109) — the number of blocks in each box.

It's guaranteed that the sum of n over test cases doesn't exceed 105.

Output 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.

Example inputCopy 3 3 3 2 2 4 2 2 3 2 3 0 3 0 outputCopy 1 0 3 Note 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].

B、 玩具积木

每次测试的时间限制2秒

每次测试的内存限制256兆字节

输入标准输入

输出标准输出

你被要求观察你的侄子，他喜欢用一种奇怪的方式玩玩具积木。

他有n个盒子，第i个盒子有ai积木。他的游戏包括两个步骤：

他选择了一个任意的盒子i；

他试图把第i个盒子里的所有积木移到其他盒子里。

如果他能在其他n-1个盒子里做同样数量的积木，那么他会高兴，否则，他会伤心。请注意，您的侄子只能将方块从所选方块移到其他方块；他无法从其他方块移动方块。

你不想让你的侄子伤心，所以你决定在一些盒子里多放几个积木，这样无论他选择哪个盒子，他都不会伤心。你最少需要多放几块？

输入

第一行包含单个整数t（1≤t≤1000）——测试用例的数量。

每个测试用例的第一行包含整数n（2≤n≤105）——盒子的数量。

每个测试用例的第二行包含n个整数a1，a2，…，an（0≤ai≤109）-每个框中的块数。

保证n个以上测试用例之和不超过105个。

输出

对于每个测试用例，打印一个整数-您需要放置的最小块数。可以证明答案总是存在的，即块的数目是有限的。

例子

输入副本

三

三

3 2 2

4

2 2 3 2

三

0 3 0

输出副本

1

0

三

注意

例如，在第一个测试用例中，可以将一个额外的块放入第一个框中，并使a=[4,2,2]。如果您的侄子选择有4个方块的盒子，那么我们将移动两个方块到第二个方块，两个方块移到第三个方块。如果他选择有两个方块的盒子，他会把这两个方块移到另一个有两个方块的盒子。

在第二个测试用例中，您不需要放置任何额外的块，因为无论您的侄子选择哪个框，他总是可以使其他框相等。

在第三个测试用例中，您应该额外放置3个块。例如，可以在第一个框中放置2个块，在第三个框中放置1个块。您将得到数组a=[2,3,1]。