给定一个大小为 $$$n$$$ 的数组 $$$a$$$,你可以对数组 $$$a$$$ 执行以下操作任意次数(包括零次):
- 选择任意一组 $$$k$$$ 不同索引 $$$S = \{i_1, i_2, \ldots, i_k\}$$$,其中 $$$1 \le i_j \le n$$$ 对于所有 $$$1\le j\le k$$$。
- 计算总和 $$$x = a_{i_1} + a_{i_2} + \cdots + a_{i_k}$$$,并设置 $$$y = x - \left\lfloor \frac{x}{k} \right\rfloor \cdot k$$$。
- 在所选元素$$$a_{i_1}、\ldots、a_{i_k}$$$中,将$$$y$$$最小值减少$$$1$$$。
- 如果两个元素具有不同的值 ($$$a_i\ne a_j$$$),则值较小的元素较小。
- 如果两个元素具有相同的值 ($$$a_i= a_j$$$),则索引较小的元素较小。
- 如果$$$y=0$$$,则不减少任何元素。
您的任务是确定在执行任意次操作后可以达到的数组 $$$a$$$ 元素总和的最小可能值,或者报告它可以无限期减小。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,打印执行上述操作任意次数后可以达到的数组 $$$a$$$ 元素总和的最小可能值。
如果数组 $$$a$$$ 的元素总和可以无限减少,则打印 $$$-1$$$。
示例
输入复制
322 143 3 3 381 2 3 4 5 6 7 8
输出复制
212-1
注意
在第一个测试用例中,我们只能对整个数组执行一次操作,这会导致数组 $$$a = [2, 0]$$$,之后任何操作都不会导致数组减少。
在第二个测试用例中,没有任何操作会导致减少,因此,答案是给定数组元素的总和。
在第三个测试用例中,存在一系列操作,允许我们无限期地减少数组元素的总和。