Minimum Removal for Divisibility

You are given an array of integers. Your task is to remove exactly one element from the array such that the sum of the remaining elements is divisible by \(n-1\), where \(n\) is the number of elements in the array.

More formally, let \(A = [a_1, a_2, \dots, a_n]\) and \(S = a_1+a_2+\cdots+a_n\). You need to find an element \(x\) from \(A\) such that \(S-x\) is divisible by \(n-1\), that is, \[ S - x \equiv 0 \pmod{n-1}. \] If there are multiple valid choices, you must output the smallest such \(x\). If no such element exists, print -1.

Note: The input is given in the form of multiple test cases in a single run. For each test case, first an integer \(n\) is given, followed by a line of \(n\) integers.

inputFormat

The first line of input contains an integer \(T\) (the number of test cases). Each test case consists of two lines:

• The first line contains an integer \(n\) (\(n \ge 2\)).
• The second line contains \(n\) space-separated integers.

All input is read from standard input (stdin).

outputFormat

For each test case, output one line containing the minimum integer that can be removed such that the sum of the remaining elements is divisible by \(n-1\). If no such element exists, output -1.

All output should be written to standard output (stdout).

## sample

4
4
1 2 3 4
5
1 -1 1 -1 2
3
1 2 3
4
1 2 4 5

1
2
2
-1

</p>