F. Sum Minimisation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$, and you can perform the following operation on the array $$$a$$$ any number of times (including zero):

  1. Select any set of $$$k$$$ distinct indices $$$S = \{i_1, i_2, \ldots, i_k\}$$$, where $$$1 \le i_j \le n$$$ for all $$$1\le j\le k$$$.
  2. Compute the sum $$$x = a_{i_1} + a_{i_2} + \cdots + a_{i_k}$$$, and set $$$y = x - \left\lfloor \frac{x}{k} \right\rfloor \cdot k$$$.
  3. Among the selected elements $$$a_{i_1}, \ldots, a_{i_k}$$$, decrease the $$$y$$$ smallest values by $$$1$$$.
    • If two elements have different values ($$$a_i\ne a_j$$$), the one with the smaller value is smaller.
    • If two elements have the same value ($$$a_i= a_j$$$), the one with the smaller index is smaller.
    • If $$$y=0$$$, no element is decreased.

Your task is to determine the minimum possible value of the sum of elements of the array $$$a$$$ that can be achieved after performing the operation any number of times or report that it can be decreased indefinitely.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array $$$a$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each testcase, print the minimum possible value of the sum of elements of the array $$$a$$$ that can be achieved after performing the above mentioned operation any number of times.

If the sum of elements of the array $$$a$$$ can be decreased indefinitely, print $$$-1$$$.

Example
Input
3
2
2 1
4
3 3 3 3
8
1 2 3 4 5 6 7 8
Output
2
12
-1
Note

In the first testcase, we can perform only one operation once on the whole array, which leads to the array $$$a = [2, 0]$$$, after which no operation leads to a decrease.

In the second testcase, no operation leads to a decrease and thus, the answer is the sum of the array elements given.

In the third test case, there exists a sequence of operations that will allow us to decrease the sum of elements of the array indefinitely.