Toy Blocks

题意翻译

### 题目描述 你被叫去照看你的一个喜欢以一种奇怪方法玩积木的侄子。 你的侄子有 $n$ 个盒子，第 $i$ 个盒子中有 $a_i$ 个积木。他的游戏由两步组成： 1. 随机选择一个盒子 $i$ ； 2. 将第 $i$ 个盒子中的所有积木转移到其他盒子中。 两步操作后，如果他可以使其他 $n-1$ 个盒子中积木的数量相同，他就会高兴，否则他将伤心。注意：你的侄子只能将积木从被选中的盒子中转移到其他盒子；他不能从其他盒子中移动积木。你不想让你的侄子伤心，所以你打算在一些盒子中额外放几个积木，使得不论你的侄子选择任何盒子，他都不会伤心。求出最少额外放入的积木数。 ### 输入格式 第一行一个正整数 $t$ $( 1 \leq t \leq 1000 )$ 是测试点数量。 每个测试点中： 第一行一个正整数 $n$ $( 1 \leq n \leq 10^5 )$ 是盒子的数量。 第二行 $n$ 个正整数 $a_1 , a_2 , ...... , a_n$ $(0 \leq a_i \leq 10^9)$ 是每个盒子中积木的数量。 ### 输出格式 每行一个最少额外放入的积木数。 ### 说明/提示 在第一个测试点中，你可以在第一个盒子中放 $1$ 个积木。 在第二个测试点中，你不需要放积木。 在第三个测试点中，你可以在第一个盒子中放 $2$ 个积木，在第三个盒子中放 $1$ 个积木。

题目描述

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?

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

3
3
3 2 2
4
2 2 3 2
3
0 3 0

输出样例 #1

1
0
3

说明

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] $ .