J. Completely Balanced
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Omar is an AI engineer who is studying statistics. Recently, he knew about $$$mean$$$ and $$$median$$$.

His curiosity makes him wonder, if you have an array $$$a$$$ of $$$n$$$ integers, can you add just one integer $$$\bf{X}$$$ such that the $$$mean$$$ and the $$$median$$$ of the updated array would be equal?

Where the $$$mean$$$ of an array $$$a$$$ equals: $$$\frac{\sum_{i = 1}^n a_i}{n}$$$. The $$$mean$$$ of the array $$$[2, 6, 1, 2, 4]$$$ is $$$\frac{2+6+1+2+4}{5} = 3$$$.

A $$$median$$$ of an array of $$$n$$$ numbers is the element which occupies position number $$$\lfloor \frac{n+1}{2} \rfloor$$$ after we sort the elements in the non-decreasing order (the array elements are numbered starting from 1). The $$$median$$$ of the array $$$[2, 6, 1, 2, 3]$$$ is $$$2$$$, and the $$$median$$$ of the array $$$[0, 96, 17, 23]$$$ is 17.

We define an expression $$$\lfloor \frac{a}{b} \rfloor$$$ as the integer part of dividing number $$$a$$$ by number $$$b$$$.

It's guaranteed that The answer is always exists under the given constraints

Input

The first line contains $$$1 \le T \le 1000$$$ number of test cases.

For each test case, you will be given an integer $$$1 \le n \le 10^6$$$ followed by $$$n$$$ integers $$$-10^9 \le a_i \le 10^9$$$.

It is guaranteed that the sum of n over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, you have to print one integer $$$\bf{X}$$$ that solves the problem.

If there are multiple solutions print the minimum one.

Example
Input
2
2
2 3
5
1 2 3 4 6
Output
1
-4
Note

In the first test case, the updated array will be [1, 2, 3], $$$mean$$$ = $$$median$$$ = 2.

In the second test case, the updated array will be [-4, 1, 2, 3, 4, 6], $$$mean$$$ = $$$median$$$ = 2.