旅行者矮人決定今年專注於征服弗羅茨瓦夫的山峰。他最新的目標是在連續的 $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