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:
t=int(input())
for _ in range(t):
    n=int(input())
    arr= list(map(int,input().split()))
    ans=[]
    arr.sort()
    if (n%2==0):
        ans.append(arr[int(n/2)-1])
        ans.append(arr[int(n/2)])
        for i in range(1,int(n/2)):
            ans.append(arr[int(n/2)-i-1])
            ans.append(arr[int(n/2)+i])
    else:
        ans.append(arr[int(n/2)])
        for i in range(1,int(n/2)+1):
            ans.append(arr[int(n/2)-i])
            ans.append(arr[int(n/2)+i])
    
    print(*ans,sep=" ")





# t=int(input())
# for _ in range(t):
#     n=int(input())
#     arr=list(map(int,input().split()))
#     c=0
#     s=[0]*(n-1)
#     arr.sort()
#     ans=[]
#     for i in range(1,n):
#         s[i-1]=abs(arr[i]-arr[i-1])
#     # print(s)
#     ans.append(arr[s.index(min(s))])
#     ans.append(arr[(s.index(min(s)))+1])
#     print(arr)
#     arr.pop(arr.index(ans[0]))
#     arr.pop(arr.index(ans[1]))
#     print(arr)
#     i=n-len(ans)
#     while i>0:
#         mi=float("inf")
#         for j in arr:
#             if abs(ans[len(ans)-1]-j)<=mi:
#                 e=j
#                 mi =  abs(ans[len(ans)-1]-j)
#         ans.append(e)
#         arr.pop(arr.index(e))
#         i-=1
#     print(*ans,sep=" ")
        
            
        

# # t=int(input())
# # for _ in range(t):
# #     n=int(input())
# #     arr=list(map(int,input().split()))
# #     c=0
# #     s=[]
# #     for i in range(n):
# #         e1=-1
# #         e2=-1
# #         i-=c
# #         mi=float("inf")
# #         for j in range(i+1,len(arr)):
# #             print(i,j)
# #             if i==j:
# #                 continue
# #             else:
# #                 # print(arr[i]-arr[j],mi)
# #                 if abs(arr[i]-arr[j])<=mi:
# #                     mi=abs(arr[i]-arr[j])
# #                     e1=arr[i]
# #                     e2=arr[j]
# #                 # print('mi',mi)
# #         print(arr,e1,e2,s,mi)
# #         arr.pop(arr.index(e1))
# #         arr.pop(arr.index(e2))
# #         c+=2
# #         s.append(e1)
# #         s.append(e2)
# #     print(s)