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 PYTHON3):

Solution:
import sys
import os
from io import BytesIO, IOBase

#########################
# imgur.com/Pkt7iIf.png #
#########################

# returns the list of prime numbers less than or equal to n:
'''def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r'''

# returns all the divisors of a number n(takes an additional parameter start):
def divs(n, start=1):
    divisors = []
    for i in range(start, int(n**.5) + 1):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return len(divisors)

# returns the number of factors of a given number if a primes list is given:
'''def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
    return divs_number'''

# returns the leftmost and rightmost positions of x in a given list d(if x isnot present then returns (-1,-1)):
'''def flin(d, x, default=-1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return (default, default)
    else:
        return (left, right)'''

#count xor of numbers from 1 to n:
'''def xor1_n(n):
    d={0:n,1:1,2:n+1,3:0}
    return d[n&3]'''

def cel(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return defaultdict(int)
def ddl(): return defaultdict(list)
def ddd(): return defaultdict(defaultdict(int))

# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
	newlines = 0
 
	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None
 
	def read(self):
			while True:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					if not b:
							break
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines = 0
			return self.buffer.read()
 
	def readline(self):
			while self.newlines == 0:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					self.newlines = b.count(b"\n") + (not b)
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines -= 1
			return self.buffer.readline()
 
	def flush(self):
			if self.writable:
					os.write(self._fd, self.buffer.getvalue())
					self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
	def __init__(self, file):
			self.buffer = FastIO(file)
			self.flush = self.buffer.flush
			self.writable = self.buffer.writable
			self.write = lambda s: self.buffer.write(s.encode("ascii"))
			self.read = lambda: self.buffer.read().decode("ascii")
			self.readline = lambda: self.buffer.readline().decode("ascii")
 

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

from collections import defaultdict 
#from collections import deque
#from collections import OrderedDict
#from math import gcd
#import time
#import itertools
#import timeit
#import random
#from bisect import bisect_left as bl
#from bisect import bisect_right as br
#from bisect import insort_left as il
#from bisect import insort_right as ir
#from heapq import *
#mod=998244353
#mod=10**9+7
# for counting path pass prev as argument:
# for counting level of each node w.r.t to s pass lvl instead of prev:

 
'''for _ in range(ii()):
    s=input()
    n0,n1,na,nA=1,1,1,1
    brk=[]
    op=[]
    cnt=0
    for i in s:
        if i=='#':
            cnt+=1
        elif i in ['|','&','^']:
            op.append(i)
        elif i==')':
            ch=op.pop()
            if ch=='|':
                tmp0,tmp1,tmpa,tmpA=n0,n1,na,nA
                tmp1=n0+4*n1+2*(na+nA)
                tmpa=n0+2*(na)
                tmpA=n0+2*(nA)
                n0,n1,na,nA=tmp0,tmp1,tmpa,tmpA
            elif ch=='&':
                tmp0,tmp1,tmpa,tmpA=n0,n1,na,nA
                tmp0=n1+4*n0+2*(na+nA)
                tmpa=n1+2*(na)
                tmpA=n1+2*(nA)
                n0,n1,na,nA=tmp0,tmp1,tmpa,tmpA
            elif ch=='^':
                tmp0,tmp1,tmpa,tmpA=n0,n1,na,nA
                tmp0=(n0+n1+na+nA)
                tmp1=(n0+n1+na+nA)
                tmpa=(n0+n1+na+nA)
                tmpA=(n0+n1+na+nA)
                n0,n1,na,nA=tmp0,tmp1,tmpa,tmpA
    dn=pow(4,(cnt*(mod-2))%(mod-1),mod)
    ans0=(n0*dn)%mod
    ans1=(n1*dn)%mod
    ansa=(na*dn)%mod
    ansA=(nA*dn)%mod
    print(ans0,ans1,ansa,ansA)'''

for _ in range(ii()):
    n=ii()
    a=li()
    a.sort()
    l,r=0,n-1
    res=[0 for i in range(n)]
    j=n-1
    while(l<=r):
        res[j]=a[r]
        if j>0:
            res[j-1]=a[l]
        j-=2
        l+=1
        r-=1
    print(*res)