Minimize Maximum Difference

You are given T test cases. For each test case, you are given an integer N followed by N integers. For each test case, your task is to choose an integer (X) such that the maximum absolute difference between (X) and any element in the array is minimized. Formally, given an array (a_1, a_2, \dots, a_N), you need to find an integer (X) which minimizes (\max_{1 \le i \le N} |X - a_i|).

A common strategy is to first sort the array. If (N) is odd, the median (a_{\frac{N+1}{2}}) is a good candidate. If (N) is even, one acceptable answer is (\left\lfloor \frac{a_{\frac{N}{2}} + a_{\frac{N}{2}+1}}{2} \right\rfloor) (using integer division). This is the approach you are expected to implement.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer (T), the number of test cases.
  
• For each test case, the first line contains an integer (N), the number of elements in the array.
  
• The next line contains (N) space-separated integers representing the array.

outputFormat

For each test case, output the chosen integer (X) on a separate line. The output is written to standard output (stdout).## sample

2
5
1 5 9 12 15
3
4 6 7

9
6