Problem: You have array of n numbers a_{1}, a_{2}, …, a_{n}. 

Rearrange these numbers to satisfy |a_{1} - a_{2}| ≤ |a_{2} - a_{3}| ≤ … ≤ |a_{n-1} - a_{n}|, where |x| denotes absolute value of x. It's always possible to find such rearrangement.

Note that all numbers in a are not necessarily different. In other words, some numbers of a may be same.

You have to answer independent t test cases.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^{4}) — the number of test cases.

The first line of each test case contains single integer n (3 ≤ n ≤ 10^{5}) — the length of array a. It is guaranteed that the sum of values of n over all test cases in the input does not exceed 10^{5}.

The second line of each test case contains n integers a_{1}, a_{2}, …, a_{n} (-10^{9} ≤ a_{i} ≤ 10^{9}).

Output

For each test case, print the rearranged version of array a which satisfies given condition. If there are multiple valid rearrangements, print any of them.

Example

Input


2
6
5 -2 4 8 6 5
4
8 1 4 2


Output


5 5 4 6 8 -2
1 2 4 8

Note

In the first test case, after given rearrangement, |a_{1} - a_{2}| = 0 ≤ |a_{2} - a_{3}| = 1 ≤ |a_{3} - a_{4}| = 2 ≤ |a_{4} - a_{5}| = 2 ≤ |a_{5} - a_{6}| = 10. There are other possible answers like "5 4 5 6 -2 8".

In the second test case, after given rearrangement, |a_{1} - a_{2}| = 1 ≤ |a_{2} - a_{3}| = 2 ≤ |a_{3} - a_{4}| = 4. There are other possible answers like "2 4 8 1".

Solution (in PYTHON):

Solution:
__author__ = 'Devesh Bajpai'

'''
https://codeforces.com/problemset/problem/1339/B

Solution: Sort the array. Keep 2 pointers left and right. Take the pair of elements of these pointed elements
in the result array. Move the left leftwards and right rightwards. This ensures the net distance on the 
number line is smallest, thereby agreeing to the constraint of absolute differences of pair elements.

For odd length arrays, we keep the middle element as the first element in the result array since it cannot
be paired. And then we start from the pointers movement as mentioned above.  
'''


def solve(n, arr):

    arr.sort()

    result = [None] * n

    if n % 2 == 0:
        left = n/2 - 1
        right = n/2
        i = 0
    else:
        left = (n-1)/2 - 1
        right = (n-1)/2 + 1
        result[0] = arr[n/2]
        i = 1

    while left >= 0 and right < n:

        result[i] = arr[left]
        i += 1
        left -= 1

        result[i] = arr[right]
        i += 1
        right += 1

    return " ".join(str(_) for _ in result)


if __name__ == "__main__":

    t = int(raw_input())

    results = list()
    for _ in xrange(0, t):
        n = int(raw_input())
        arr = map(int, raw_input().split(" "))
        results.append(solve(n, arr))

    for result in results:
        print result