Little A has an array $a$ of length $n$, where $n$ is guaranteed to be odd.

Since Little A loves medians, he performs the following operation: each time, he chooses three consecutive numbers in the array and replaces them with their median. Specifically, he chooses any position $i$ (satisfying $1 < i < n$), removes $a_{i-1}$, $a_i$, and $a_{i+1}$, and inserts the median of these three numbers at that position.

Little A continues this operation until only one number remains in the array. The entire process requires a total of $\frac{n-1}{2}$ operations. He hopes that this final remaining number is as large as possible. Your task is to help Little A determine the maximum possible value of this number.

The definition of the median is: for an array of length $n$, after sorting it from smallest to largest, it is the number at rank $\frac{n+1}{2}$.

Input

The input contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^6$), representing the number of test cases.

For each test case: The first line contains an integer $n$ ($1 \le n < 10^5$), where $n$ is guaranteed to be odd. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that $\sum n \le 10^6$.

Output

For each test case, output the maximum possible value of the final remaining number after $\frac{n-1}{2}$ operations.

Examples

Input 1

6
1
1
3
1 2 2
5
1 3 4 5 2
7
1 2 3 5 6 7 4
9
9 9 8 2 4 4 3 5 3
9
4 4 9 2 9 5 8 3 3

Output 1

1
2
3
5
9
4

Note

Explanation of the examples: For the fourth example, for the array $A = [1, 2, 3, 5, 6, 7, 4]$, one possible sequence of operations is: $[1, 2, 3, 5, 6, 7, 4] \to [2, 5, 6, 7, 4] \to [5, 7, 4] \to [5]$. The three consecutive numbers underlined in $a_{i-1}, a_i, a_{i+1}$ represent the objects of each operation.