Zwerg der Reisende hat beschlossen, seine Aufmerksamkeit in diesem Jahr auf die Besteigung der Gipfel von Breslau zu richten. Sein neuestes Ziel ist es, an $N$ aufeinanderfolgenden Tagen $N$ verschiedene Gipfel zu besteigen, und zwar genau einen Gipfel pro Tag. Gipfel zu erklimmen ist für den Reisenden ein Kinderspiel. Er kann jeden Gipfel an jedem beliebigen Tag besteigen, weshalb er beschlossen hat, die gesamte Expedition in den Medien so öffentlichkeitswirksam wie möglich zu gestalten.

Der Zwerg hat kürzlich ein bestimmtes Muster bemerkt:

• Nach der Besteigung des ersten Gipfels ist das Medieninteresse unabhängig von dessen Höhe groß.
• Besteigt er an einem Tag einen Gipfel der Höhe $a$ und am nächsten Tag einen Gipfel der Höhe $b$, so sinkt das Medieninteresse an seiner Expedition um $\lfloor a/b \rfloor$ Einheiten, die er Medieninteresseeinheiten nennt.

Der Reisende weiß bereits, dass er $N$ Gipfel mit den Höhen $a_1, \dots, a_N$ besteigen muss. Zudem stellt sich heraus, dass die Höhe des höchsten Gipfels höchstens doppelt so groß ist wie die Höhe des niedrigsten. Der Zwerg kann die Reihenfolge der Gipfel beliebig wählen. Sein Ziel ist es, den Gesamtrückgang an Medieninteresseeinheiten während der gesamten Expedition zu minimieren.

Kannst du ihm helfen, die Reihenfolge für den Besuch aller Gipfel so zu wählen, dass der Rückgang an Medieninteresseeinheiten minimiert wird?

Eingabe

Die erste Zeile der Eingabe enthält die Zahl $T$, die Anzahl der Testfälle.

Die erste Zeile jedes Testfalls enthält eine einzelne ganze Zahl $N$, die Anzahl der Gipfel, die der Reisende besuchen wird.

Die zweite Zeile des Testfalls enthält $N$ ganze Zahlen $a_1, \dots, a_N$, welche die in der Aufgabe genannten Bedingungen erfüllen.

Ausgabe

Gib für jeden Testfall zwei Zeilen aus. Die erste Zeile soll eine einzelne ganze Zahl enthalten, die den minimal möglichen Rückgang an Medieninteresseeinheiten für die Reise des Zwergs darstellt.

Die zweite Zeile soll die Höhen $a_1, \dots, a_N$ in der Reihenfolge enthalten, in der der Zwerg sie besuchen sollte, um diesen minimalen Rückgang zu erreichen.

Gibt es mehrere optimale Lösungen, kannst du eine beliebige davon ausgeben.

Beschränkungen

$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\}$, die Summe der Werte von $N$ in der Eingabe überschreitet $10^6$ nicht.

Beispiele

Eingabe 1

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

Ausgabe 1

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