Krasnal Podróżnik postanowił w tym roku skupić swoją uwagę na zdobywaniu szczytów Wrocławia. Jego najnowszym celem jest zdobycie $N$ różnych szczytów w ciągu $N$ kolejnych dni, dokładnie jednego szczytu każdego dnia. Zdobywanie szczytów to dla Podróżnika bułka z masłem. Może zdobyć dowolny szczyt w dowolnym dniu, dlatego postanowił zadbać o to, by cała wyprawa odbiła się jak najszerszym echem w mediach.

Krasnal zauważył ostatnio pewną prawidłowość:

• Po zdobyciu pierwszego szczytu zainteresowanie mediów będzie wysokie, niezależnie od jego wysokości.
• Jeśli jednego dnia zdobędzie szczyt o wysokości $a$, a następnego dnia szczyt o wysokości $b$, to zainteresowanie mediów jego wyprawą spada o $\lfloor a/b \rfloor$ jednostek, które nazywa on jednostkami zainteresowania mediów.

Podróżnik wie już, że będzie musiał zdobyć $N$ szczytów o wysokościach $a_1, \dots, a_N$. Co więcej, okazuje się, że wysokość najwyższego szczytu jest co najwyżej dwa razy większa od wysokości najniższego. Krasnal może wybrać kolejność szczytów dowolnie. Jego celem jest zminimalizowanie łącznego spadku jednostek zainteresowania mediów podczas całej wyprawy.

Czy pomożesz mu wybrać kolejność odwiedzania wszystkich szczytów tak, aby spadek jednostek zainteresowania mediów był jak najmniejszy?

Wejście

Pierwszy wiersz wejścia zawiera liczbę $T$, oznaczającą liczbę zestawów testowych.

Pierwszy wiersz każdego zestawu testowego zawiera jedną liczbę całkowitą $N$, oznaczającą liczbę szczytów do odwiedzenia przez Podróżnika.

Drugi wiersz zestawu testowego zawiera $N$ liczb całkowitych $a_1, \dots, a_N$, spełniających warunki podane w zadaniu.

Wyjście

Dla każdego zestawu testowego wypisz dwa wiersze. Pierwszy wiersz powinien zawierać jedną liczbę całkowitą oznaczającą minimalny możliwy spadek jednostek zainteresowania mediów podczas podróży krasnala.

Drugi wiersz powinien zawierać wysokości $a_1, \dots, a_N$ ustawione w kolejności, w jakiej Krasnal powinien je odwiedzać, aby osiągnąć ten minimalny spadek.

Jeśli istnieje wiele rozwiązań optymalnych, możesz wypisać dowolne z nich.

Ograniczenia

$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\}$, suma wartości $N$ podanych na wejściu nie przekracza $10^6$.

Przykłady

Wejście 1

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

Wyjście 1

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