说明

未来的战争是科技的战争。假如A国受到B国的导弹威胁，那么A国就要启用导弹防御系统，根据卫星、雷达信息快速计算出敌方弹道导弹发射点和落点的信息，将导弹的跟踪和评估数据转告地基雷达，发射拦截导弹摧毁敌方导弹或使导弹失去攻击能力。如果A国的导弹防御系统处理速度缓慢，等算出结果时，导弹已经落地了，还谈何拦截？

现代科技的发展，速度至关重要。以最基本的排序为例，生活中到处都用到排序，例如各种比赛、奖学金评选、推荐系统等，排序算法有很多种，能不能找到更快速高效的排序算法呢？ 快速排序（Quicksort）是比较快速的排序方法。给定$n$个元素，进行快速排序（非递减）。

输入格式

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

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

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

输出格式

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

每组的输出占一行

样例

2
9
30 24 5 58 18 36 12 42 39
5
8 3 48 6 12

5 12 18 24 30 36 39 42 58
3 6 8 12 48

来源

《趣学算法》3.4节