Description

给定一维int型数组a[0,1,...,n-1], 使用归并排序方法, 对其进行从小到大排序, 请输出递归过程中自顶自下第三层的排序结果, 其中最顶层为第一层, 即最终的排序结果层. 
归并排序划分请按a[0,mid=(0+n-1)/2], a[(0+n-1)/2+1, n-1]进行划分子问题.

Input

输入第1行有一个int型正整数m (m<100), 表示有m行输入.
每行输入的第一个数为int型正整数n (8<n<1000), 后面接着输入n个int型整数.

Output

输出m行, 每行为排好序的输出.

Sample Input

2
9 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1 0

Sample Output

7 8 9 5 6 3 4 1 2
7 8 9 5 6 2 3 4 0 1