Polycarp 有 $$$n$$$ 个朋友,他的第 $$$i$$$ 个朋友有 $$$a_i$$$ 糖果。坡旅甲的朋友们不喜欢他们拥有不同数量的糖果。换句话说,他们希望所有 $$$a_i$$$ 都相同。为了解决这个问题,Polycarp 仅执行一次以下一组操作:
- Polycarp 选择 $$$k$$$ ($$$0 \le k \le n$$$) 个任意朋友(假设他选择索引为 $$$i_1, i_2, \ldots, i_k$$$ 的朋友);
- Polycarp 将他们的 $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ 糖果分发给所有 $$$n$$$ 朋友。在分配每个 $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ 糖果时,他会选择新的所有者。这可以是任何 $$$n$$$ 朋友。请注意,任何糖果都可以给予在分发过程之前拥有该糖果的人。
注意,数字$$$k$$$不是预先固定的,可以是任意的。您的任务是找到 $$$k$$$ 的最小值。
例如,如果 $$$n=4$$$ 且 $$$a=[4, 5, 2, 5]$$$,则 Polycarp 可以进行以下糖果分配:
- Polycarp 选择 $$$k=2$$$ 索引为 $$$i=[2, 4]$$$ 的朋友,并分发 $$$a_2 + a_4 = 10$$$ 糖果来制作 $$$a=[4, 4, 4, 4]$$$ (两颗糖果送给 $$$3$$$ 人)。
请注意,在这个例子中,Polycarp 无法选择 $$$k=1$$$ 朋友,以便他可以重新分配糖果,以便最终所有 $$$a_i$$$ 都是相等的。
对于数据$$$n$$$ 和$$$a$$$,确定最小值$$$k$$$。有了这个值 $$$k$$$,Polycarp 应该能够选择 $$$k$$$ 朋友并重新分配他们的糖果,以便每个人最终都会得到相同数量的糖果。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例输出:
- $$$k$$$的最小值,这样Polycarp可以准确地选择$$$k$$$朋友,这样他就可以按照想要的方式重新分配糖果;
- 如果不存在这样的值 $$$k$$$,则为“-1”。
示例
输入 #1
5 4 4 5 2 5 2 0 4 5 10 8 5 1 4 1 10000 7 1 1 1 1 1 1 1
输出 #1
2 1 -1 0 0