You are given an array A of N integers. You perform this operation N−2 times: For each contiguous subarray of odd size greater than 2, you find the median of each subarray(Say medians obtained in a move are M1,M2,M3,…,Mk). In each move, you remove the first occurrence of value min(M1,M2,M3,…,Mk) from the original array. After removing the element the array size reduces by 1 and no void spaces are left. For example, if we remove element 2 from the array {1,2,3,4}, the new array will be {1,3,4}.
Print a single integer denoting the sum of numbers that are left in the array after performing the operations. You need to do this for T test cases.
Input Format
The first line contains T denoting the number of test cases(1≤T≤10).
The first line of each test case contains N denoting the number of integers in the array initially(4≤N≤105).
The next line contains N space seperated integers denoting A1,A2,A3,…,AN(1≤Ai≤109 for all valid i).
Output Format
Output a single integer denoting the sum of numbers left in the array after performing the operations for each test case on a new line.
For the first test case: Initially, array is {2,5,3,2}. The medians obtained are {3,3} for subarrays [1,3] and [2,4] respectively. Hence, we remove min(3,3)=3 from the initial array. The array now becomes {2,5,2}. The median of the whole array is 2. Hence we remove the first occurrence of 2 from the array. So, we are left with {5,2} in our array.
For the second test case, it is obvious that the minimum medium will be 1 every time. Hence finally, we will be left with {1,1} as the array.
