给定一个长度为 $n$ 的数组 $\boldsymbol{a}$，你可以对数组执行任意次下述操作（包括 $0$ 次）：

1. 选择任意 $k$ 个不同的下标集合 $S = \{i_1,i_2,\dots,i_k\}$，满足 $1\le i_j\le n$。
2. 计算和 $x = a_{i_1}+a_{i_2}+\cdots+a_{i_k}$，并计算 $y = x - \left\lfloor \dfrac{x}{k} \right\rfloor \cdot k$ （即 $y = x \bmod k$）。
3. 在选中的 $k$ 个元素中，将最小的 $y$ 个元素各减 $1$。
   • 若 $a_i \neq a_j$，值更小的元素更小；
   • 若 $a_i = a_j$，下标更小的元素更小。
4. 若 $y=0$，则不执行任何减法。

你的任务是求出：执行任意次操作后，数组元素总和的最小可能值。 如果数组总和可以无限减小，则输出 $-1$。

输入格式

多组测试用例。 第一行输入整数 $t$（$1\le t\le 10^4$），表示测试组数。

每组测试用例：

1. 第一行输入整数 $n$（$1\le n\le 10^6$），表示数组长度。
2. 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^9$）。

保证：所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对每组测试用例，输出数组总和能达到的最小可能值。 若总和可以无限减小，输出 $\boldsymbol{-1}$。

样例输入

3
2
2 1
4
3 3 3 3
8
1 2 3 4 5 6 7 8

样例输出

2
12
-1

样例说明

1. 第一组：对整个数组执行一次操作后得到 $[2,0]$，无法继续减小，总和为 $2$。
2. 第二组：任何操作都无法减小数组，答案为原数组和 $12$。
3. 第三组：存在操作序列可以让总和无限减小，答案为 $-1$。