给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$,它的所有元素都是不同的。
首先,系统会要求您在该数组中再插入一个整数 $$$a_{n+1}$$$。 $$$a_{n+1}$$$ 不应等于 $$$a_1、a_2、\dots、a_n$$$ 中的任何一个。
然后,您必须使数组的所有元素相等。首先,您选择一个正整数 $$$x$$$ ($$$x > 0$$$)。在一项操作中,您将 $$$x$$$ 添加到数组的恰好一个元素。请注意,$$$x$$$ 对于所有操作都是相同的。
在选择 $$$a_{n+1}$$$ 和 $$$x$$$ 后,最少需要多少次操作才能使所有元素相等?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。所有 $$$a_i$$$ 都是不同的。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 在选择整数 $$$a_{n+1}$$$ 和 $$$x$$$ 后,使所有元素相等所需的最少操作数。
示例
输入 #1
3 3 1 2 3 5 1 -19 17 -3 -15 1 10
输出 #1
6 27 1
注意
在第一个测试用例中,可以选择$$$a_{n+1} = 4$$$,数组变为$$$[1, 2, 3, 4]$$$。然后选择 $$$x = 1$$$ 并对第一个元素应用操作 $$$3$$$ 次,对第二个元素应用操作 $$$2$$$ 次,对第三个元素应用操作 $$$1$$$ 次,对第四个元素应用操作 $$$0$$$ 次。
在第二个测试用例中,您可以选择 $$$a_{n+1} = 13, x = 4$$$。
在第三个测试用例中,您可以选择 $$$a_{n+1} = 9, x = 1$$$。然后对 $$$a_{n+1}$$$ 应用一次操作。