题目描述

Polycarp 有 $n$ 个朋友，第 $i$ 个朋友有 $a_i$ 块糖果。Polycarp 希望他的每个朋友拥有的糖果数量相同，且他能选择任意朋友将他们的糖果以任意一种方式重新分配。求 Polycarp 最少需要选择几个朋友，将他们拥有的糖果重新分配就能达成目的。

例如 $n = 4, a = [4, 5, 2, 5]$ 时，Polycarp 可以选择 $k = 2$ 把第 $2$ 个和第 $4$ 个朋友共 $a_2 + a_4 = 10$ 个糖果重新分配后使得 $a = [4,4,4,4]$(有 $2$ 块给了第 $3$ 个朋友)，并且容易证明不存在其他更小的 $k$ 使得在重新分配后每个朋友拥有同样多的糖果。

输入格式

在输入的第一行为一个整数 $t$（$1 \le t \le {10}^4$），为数据组数。

接下来对于每组数据，第一行为一个整数 $n$（$2 \le n \le 2 \times {10}^5$），为朋友的数量；第二行有 $n$ 个整数 $a_1, a_2, \ldots , a_n$（$0 \le a_i \le {10}^4$），为每个朋友拥有的糖果数。

保证对于所有组数据 $\sum n \le 2 \times {10}^5$。

输出格式

对于每组数据，输出一个整数 $k$ 表示 Polycarp 最少需要选择的朋友数量。

如果不存在这样的 $k$，请输出 $-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

2
1
-1
0
0