旅行者矮人决定今年专注于征服弗罗茨瓦夫的山峰。他最新的目标是在连续的 $N$ 天内征服 $N$ 座不同的山峰，每天恰好征服一座。对于这位旅行者来说，征服山峰易如反掌。他可以在任何一天征服任何一座山峰，因此他决定让整个探险活动在媒体上尽可能地广为人知。

这位矮人最近注意到了一种规律：

• 在征服第一座山峰后，无论其高度如何，媒体关注度都会很高。
• 如果他在某一天征服了一座高度为 $a$ 的山峰，而在第二天征服了一座高度为 $b$ 的山峰，那么他探险活动的媒体关注度会减少 $\lfloor a/b \rfloor$ 个单位，他称之为媒体关注度单位。

旅行者已经知道他将要征服 $N$ 座高度分别为 $a_1, \dots, a_N$ 的山峰。此外，已知最高山峰的高度最多是最低山峰高度的两倍。矮人可以任意选择征服山峰的顺序。他的目标是使整个探险过程中媒体关注度单位的总减少量最小化。

你能帮他选择访问所有山峰的顺序，以使媒体关注度单位的减少量最小吗？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $N$，表示旅行者要访问的山峰数量。

每个测试用例的第二行包含 $N$ 个整数 $a_1, \dots, a_N$，满足题目中给出的条件。

输出格式

对于每个测试用例，输出两行。第一行应包含一个整数，表示矮人旅程中媒体关注度单位的最小可能减少量。

第二行应包含按矮人访问顺序排列的山峰高度 $a_1, \dots, a_N$。

如果存在多个最优解，你可以输出其中任意一个。

数据范围

$1 \le T \le 100\,000$，$1 \le N \le 10^6$，$1 \le a_i \le 10^9$，$\max\{a_1, \dots, a_N\} \le 2 \cdot \min\{a_1, \dots, a_N\}$，所有测试用例中 $N$ 的总和不超过 $10^6$。

样例

输入 1

3
6
10 18 12 13 17 14
4
10 10 7 7
8
8 4 8 5 4 4 8 6

输出 1

0
10 12 13 14 17 18
1
7 10 7 10
4
4 4 4 5 6 8 8 8