Ninja is given a few numbers, and he is being asked to rearrange the numbers so that every second element is greater than its left and right element.

Input Format:

The first line of input contains a single integer T, representing the number of test cases.

The first line of each test case contains ‘N’, denoting the number of elements in the array.

The second line of each test case contains the array elements.

Output Format :

 The first and only line of each test case in the output contains the rearranged array.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10    
1 <= N <= 10^5
0 <= array[i] <= 10^5     

Time limit: 1 second