Il nano Viaggiatore ha deciso di concentrare la sua attenzione quest'anno sulla conquista delle vette di Breslavia. Il suo ultimo obiettivo è conquistare $N$ vette diverse in $N$ giorni consecutivi, esattamente una vetta al giorno. Conquistare vette è un gioco da ragazzi per il Viaggiatore. Può conquistare qualsiasi vetta in qualsiasi giorno, motivo per cui ha deciso di rendere l'intera spedizione il più pubblicizzata possibile sui media.

Il nano ha recentemente notato un certo schema:

• Dopo aver conquistato la prima vetta, l'interesse dei media sarà alto, indipendentemente dalla sua altezza.
• Se in un giorno conquista una vetta di altezza $a$, e il giorno successivo una vetta di altezza $b$, l'interesse dei media per la sua spedizione diminuisce di $\lfloor a/b \rfloor$ unità, che egli chiama unità di interesse mediatico.

Il Viaggiatore sa già che dovrà conquistare $N$ vette di altezze $a_1, \dots, a_N$. Inoltre, risulta che l'altezza della vetta più alta è al massimo il doppio dell'altezza di quella più bassa. Il nano può scegliere l'ordine delle vette arbitrariamente. Il suo obiettivo è minimizzare la diminuzione totale in unità di interesse mediatico durante l'intera spedizione.

Puoi aiutarlo a scegliere l'ordine in cui visitare tutte le vette in modo da minimizzare la diminuzione di unità di interesse mediatico?

Input

La prima riga di input contiene il numero $T$, che rappresenta il numero di casi di test.

La prima riga di ciascun caso di test contiene un singolo intero $N$, che rappresenta il numero di vette che devono essere visitate dal Viaggiatore.

La seconda riga del caso di test contiene $N$ interi $a_1, \dots, a_N$, che soddisfano le condizioni indicate nel problema.

Output

Per ciascun caso di test, stampa due righe. La prima riga deve contenere un singolo intero che rappresenta la minima diminuzione possibile in unità di interesse mediatico per il viaggio del nano.

La seconda riga deve contenere le altezze $a_1, \dots, a_N$ disposte nell'ordine in cui il Nano dovrebbe visitarle per ottenere questa diminuzione minima.

Se esistono più soluzioni ottimali, puoi stamparne una qualsiasi.

Limiti

$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\}$, la somma dei valori di $N$ forniti in input non supera $10^6$.

Esempi

Input 1

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

Output 1

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