You are given an array A of length N.  You take an array B of length N such that B[i] = 0 for each 1 <= i <= N. You can apply the following operation on B any number of times:

• Choose (N - 1) distinct indices and add 1 to each of those indices.

Task

Find the number of operations required to convert array B into array A by applying the given operation. Print -1 if it is impossible to do so.

Function description

Complete the function solve() provided in the editor. This function takes the following two parameters and returns the required answer:

• N: Represents the length of array A.
• A: Represents the array A.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains T, denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • The first line contains N, denoting the size of array A.
  • The second line contains N space-separated integers A[1], A[2], ....., A[N], denoting the elements of  array A.

Output format
For each test case, print the number of operations required to convert array B into array A by applying the given operation or -1 if it is impossible to do so.

Constraints

\(1 \leq T \leq 10^4 \\ 2 \leq N \leq 10^5\\ \\0\leq A_i \le 10^{9} \\ \text{Sum of $N$ over all test cases does not exceed }2\cdot 10^5\)