B"Mocha likes arrays, so before her departure, Chamo gave her an array a consisting of n positive integers as a gift. Mocha doesn't like arrays containing different numbers, so Mocha decides to use magic to change the array. Mocha can perform the following three-step operation some (possibly, zero) times: Suppose a=[1,2,3,4,5] initially: Mocha will perform the operation until the array contains only the same number. Mocha wants to know what is the maximum possible value of this number. ^ dagger The median in an array b of length m is an element that occupies position number lfloor frac{m+1}{2} rfloor after we sort the elements in non-decreasing order. For example, the median of [3,1,4,1,5] is 3 and the median of [5,25,20,24] is 20 . Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= q t <= q 500 ). The description of the test cases follows. The first line of each test case contains a single integer n ( 2 <= q n <= q 10^5 ) -- the length of the array a . The second line of each test case contains n integers a_1,a_2, ldots,a_n ( 1 <= q a_i <= q 10^9 ) -- the elements of the array a . It is guaranteed that the sum of n over all test cases does not exceed 10^5 . For each test case, output the maximum value of the number. In the first test case, a=[1,2] . Mocha can only choose the interval (l,r)=(1,2) . The array will be changed to a=[1,1] . Therefore, the answer is 1 . In the second test case, Mocha can perform the following operations: The array contains only the same number, which is 4 . It can be proven that the maximum value of the final number cannot be greater than 4 . "...