Find Array Medians

You are given a collection of arrays of integers. For each array, you need to find its median. The median is defined as follows:

If an array has an odd number of elements, the median is the middle element after sorting the array. If an array has an even number of elements, the median is the smaller of the two middle elements after sorting the array. Formally, for an array \(A = [a_1, a_2, \dots, a_n]\) (after sorting in non-decreasing order), the median \(m\) is given by:

\[ m = \begin{cases} a_{\left(\frac{n+1}{2}\right)} & \text{if } n \text{ is odd},\\ a_{\left(\frac{n}{2}\right)} & \text{if } n \text{ is even.} \end{cases} \]

Your task is to compute and output the medians of each array.

inputFormat

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

1. An integer \(T\) representing the number of arrays.
2. For each array:
   1. An integer \(n\) representing the number of elements in the array.
   2. A line containing \(n\) integers separated by spaces.

You can assume that \(1 \leq T \leq 10^4\) and each array contains at least one element.

outputFormat

Output a single line containing \(T\) integers which are the medians of the corresponding arrays, separated by a single space. The output is written to standard output (stdout).

## sample

1
5
1 3 5 7 9

5

</p>