Dvergen den Reisende har bestemt seg for å rette oppmerksomheten sin i år mot å bestige toppene i Wrocław. Hans nyeste mål er å bestige $N$ forskjellige topper i løpet av $N$ påfølgende dager, nøyaktig én topp hver dag. Å bestige topper er barnemat for den Reisende. Han kan bestige hvilken som helst topp på hvilken som helst dag, og derfor har han bestemt seg for å gjøre hele ekspedisjonen så godt omtalt i mediene som mulig.

Dvergen har nylig lagt merke til et bestemt mønster:

• Etter å ha besteget den første toppen vil medieinteressen være høy, uavhengig av høyden dens.
• Hvis han én dag bestiger en topp med høyde $a$, og neste dag en topp med høyde $b$, reduseres medieinteressen for ekspedisjonen hans med $\lfloor a/b \rfloor$ enheter, som han kaller medieinteresseenheter.

Den Reisende vet allerede at han må bestige $N$ topper med høyder $a_1, \dots, a_N$. I tillegg viser det seg at høyden på den høyeste toppen er høyst dobbelt så stor som høyden på den laveste. Dvergen kan velge rekkefølgen på toppene fritt. Målet hans er å minimere den totale reduksjonen i medieinteresseenheter i løpet av hele ekspedisjonen.

Kan du hjelpe ham med å velge rekkefølgen for å besøke alle toppene slik at reduksjonen i medieinteresseenheter minimeres?

Inndata

Den første linjen i inndataen inneholder tallet $T$, som representerer antallet testtilfeller.

Den første linjen i hvert testtilfelle inneholder et enkelt heltall $N$, som representerer antallet topper som skal besøkes av den Reisende.

Den andre linjen i testtilfellet inneholder $N$ heltall $a_1, \dots, a_N$, som oppfyller betingelsene oppgitt i oppgaven.

Utdata

For hvert testtilfelle skal du skrive ut to linjer. Den første linjen skal inneholde et enkelt heltall som representerer den minste mulige reduksjonen i medieinteresseenheter for dvergens reise.

Den andre linjen skal inneholde høydene $a_1, \dots, a_N$ ordnet i den rekkefølgen Dvergen bør besøke dem for å oppnå denne minimale reduksjonen.

Hvis det finnes flere optimale løsninger, kan du skrive ut hvilken som helst av dem.

Begrensninger

$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\}$, summen av verdiene av $N$ oppgitt i inndataen overstiger ikke $10^6$.

Eksempler

Inndata 1

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

Utdata 1

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