Minimizing Absolute Differences

You are given T test cases. For each test case, you are given an integer n and an array A = [a_1, a_2, ..., a_n]. Your task is to find the smallest integer X that minimizes the function

$$ f(X) = \sum_{i=1}^{n} |a_i - X| $$

It is known that the median of the array minimizes the sum of absolute differences. In this problem, if there are two medians, choose the smaller one.

Note: Input is taken from stdin and output should be printed to stdout, with each test case's answer printed on a separate line.

inputFormat

The first line contains an integer T, denoting the number of test cases. For each test case, the first line contains an integer n — the number of elements in the array. The second line contains n space-separated integers representing the array A.

outputFormat

For each test case, output the smallest integer X that minimizes the sum of absolute differences, each on a separate line.

1
4
1 2 3 4

2