Polycarp 得到了一个整数数组 $$$a[1 \dots n]$$$ 作为礼物。现在他想要执行一定次数的操作(可能为零),使数组的所有元素变得相同(即变成$$$a_1=a_2=\dots=a_n$$$)。
- 在一次操作中,他可以获取数组中的一些索引,并将这些索引处的数组元素增加 $$$1$$$。
例如,令 $$$a=[4,2,1,6,2]$$$。他可以执行以下操作:选择索引 1、2 和 4,并将这些索引中的数组元素增加 $$$1$$$。结果,一次操作,他就可以得到数组$$$a=[5,3,1,7,2]$$$的一个新状态。
最少需要多少次操作才能使数组的所有元素变得彼此相等(即变成 $$$a_1=a_2=\dots=a_n$$$)?
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
以下是输入测试用例的描述。
每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 数组 $$$a$$$。
每个测试用例描述的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
输出
对于每个测试用例,打印一个整数 - 使数组 $$$a$$$ 的所有元素相等的最少操作数。
示例
输入 #1
3 6 3 4 2 4 1 2 3 1000 1002 998 2 12 11
输出 #1
3 4 1
注意
第一个测试用例:
- $$$a=[3,4,2,4,1,2]$$$ 对 $$$a_3, a_5$$$ 进行加一运算,得到 $$$a=[3,4,3,4,2,2]$$$。
- $$$a=[3,4,3,4,2,2]$$$ 我们对 $$$a_1, a_5, a_6$$$ 进行运算加一,结果我们得到 $$$a=[4,4,3,4,3,3]$$$。
- $$$a=[4,4,3,4,3,3]$$$ 我们对 $$$a_3, a_5, a_6$$$ 进行运算加一,结果我们得到 $$$a=[4,4,4,4,4,4]$$$。
还有其他 $$$3$$$ 操作序列,在应用这些操作之后,所有元素都变得相等。
第二个测试用例:
- $$$a=[1000,1002,998]$$$ 两次,我们对 $$$a_1, a_3$$$ 执行加一操作,结果我们得到 $$$a=[1002,1002,1000]$$$。
- $$$a=[1002,1002,1000]$$$同样对$$$a_3$$$进行2次加一运算,得到$$$a=[1002,1002,1002]$$$。
第三个测试用例:
- $$$a=[12,11]$$$ 对 $$$a_2$$$ 进行加一运算,得到 $$$a=[12,12]$$$。