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 \(M_1, M_2, M_3,\ldots, M_k\)). In each move, you remove the first occurrence of value \(min(M_1, M_2, M_3,\ldots, M_k)\) 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 \le T \le 10\)). 

The first line of each test case contains \(N\) denoting the number of integers in the array initially(\(4 \le N \le 10^5\)).

The next line contains \(N\) space seperated integers denoting \(A_1, A_2, A_3,\ldots, A_N\)(\(1 \le A_i \le 10^9\) 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.