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:
from math import floor

t = input()
t = int(t)
ar = []
res = []
for i in range(t):
    input()
    data = input()
    ar.append(data.split())
    ar[i] = list(map(int, ar[i]))

for i in range(len(ar)):
    res.append([])

maz = abs(ar[i][0] - ar[i][1])
i1 = 0
i2 = 1
# print(ar)
# for i in range(len(ar)):
#     for x1 in range(len(ar[i])):
#         for x2 in range(len(ar[i])):
#             if x1 != x2:
#                 dif = abs(ar[i][x1] - ar[i][x2])
#                 if dif < maz:
#                     maz = dif
#                     i1 = x1
#                     i2 = x2
#     first = ar[i][i1]
#     second = ar[i][i2]
#     res[i].append(first)
#     res[i].append(second)
#     if i1 < i2:
#         i2 -= 1
#     del ar[i][i1]
#     del ar[i][i2]
#     while len(ar[i]) > 1:
#         maz = abs(second - ar[i][0])
#         i2 = 0
#         for j in range(len(ar[i])):
#             dif = abs(second - ar[i][j])
#             if dif < maz:
#                 maz = dif
#                 i2 = j
#         # print(str(first) + " " + str(ar[i][index2]) + " Maz: " + str(maz))
#         # print(str(i) + str(ar[i][index2]))
#         res[i].append(ar[i][i2])
#         second = ar[i][i2]
#         del ar[i][i2]
#     else:
#         res[i].append(ar[i][0])

for i in range(t):
    ar[i].sort()
    #print(ar[i])
    i1 = floor(int(len(ar[i]) / 2)) - 1
    i2 = i1 + 1
    while i1 > -1 and i2 < len(ar[i]):
        res[i].append(ar[i][i2])
        res[i].append(ar[i][i1])
        i1 -= 1
        i2 += 1
    if len(ar[i]) % 2 != 0:
        res[i].append(ar[i][len(ar[i]) - 1])
for i in range(len(res)):
    print(*res[i], sep=' ')