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

Solution:
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class J{
	
	public static void main (String[] args )throws IOException  {
		 Scanner sc =new Scanner (System.in);
		 PrintWriter pw = new PrintWriter(System.out);
		 int t = sc.nextInt();
		while (t-- > 0 ) {
		int l = sc.nextInt();
		Integer [] arr = new Integer [l];
		for (int i = 0 ; i < l ; i ++ )  {
			arr[i] = sc.nextInt();
			
		}
//		int inc = l %2 ; 
		Arrays.sort(arr);
		int i = l/2-((l%2)^1) ; ;
		pw.print(arr[i] +  " "); i++ ; 
		if (l %2 != 0 ) {
		
		while(i <l  ) {
			pw.print(arr[i] + " " + arr[l-i-1]+ " ");
			i++ ;
		}
		if (l %2 == 0 ) pw.print(arr[l-1]);
		pw.print("\n");
		}else {while(i <l -1 ) {
			pw.print(arr[i] + " " + arr[l-i-2]+ " ");
			i++ ;
		}
		if (l %2 == 0 ) pw.print(arr[l-1]);
		pw.print("\n");
			
		}
		}
	       pw.close();
	}


	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
	}
 
 
}