旅行者矮人決定今年將注意力集中喺征服弗羅茨瓦夫嘅山峰上。佢最新嘅目標係喺連續 $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