说明

在数列排序中，如果只有一个数，那么它本身就是有序的；如果只有两个数，那么一次比较就可以完成排序。也就是说，数越少，排序越容易。那么，如果有一个由大量数据组成的数列，我们很难快速地完成排序，该怎么办呢？可以考虑将其分解为很小的数列，直到只剩一个数时，本身已有序，再把这些有序的数列合并在一起，执行一个和分解相反的过程，从而完成整个数列的排序。

合并排序就是采用分治的策略，将一个大的问题分成很多个小问题，先解决小问题，再通过小问题解决大问题。

给定$n$个元素，进行合并排序（非递减）。

输入格式

第一行是一个整型数$m(m<100)$表示共有$m$组测试数据。

每组测试数据的第一行是一个整数$n(1<n<10000)$表示该测试数据有$n$个数。

第2行，有$n$个整数$s_i(0<s_i<10000)$。

输出格式

对于每一组输入，输出排序结果（非递减）。

每组的输出占一行。

样例

2
8
42 15 20 6 8 38 50 12
5
8 3 48 6 12

6 8 12 15 20 38 42 50
3 6 8 12 48

来源

《趣学算法》3.3节