Dvärgen Resenären har bestämt sig för att i år rikta sin uppmärksamhet mot att bestiga topparna i Wrocław. Hans senaste mål är att bestiga $N$ olika toppar under $N$ på varandra följande dagar, exakt en topp varje dag. Att bestiga toppar är en barnlek för Resenären. Han kan bestiga vilken topp som helst vilken dag som helst, och därför har han beslutat att ge hela expeditionen så stor medial uppmärksamhet som möjligt.

Dvärgen har nyligen lagt märke till ett visst mönster:

• Efter att den första toppen har bestigits kommer medieintresset att vara högt, oavsett dess höjd.
• Om han en dag bestiger en topp med höjden $a$, och nästa dag en topp med höjden $b$, minskar medieintresset för hans expedition med $\lfloor a/b \rfloor$ enheter, vilket han kallar medieintresseenheter.

Resenären vet redan att han kommer att behöva bestiga $N$ toppar med höjderna $a_1, \dots, a_N$. Dessutom visar det sig att höjden på den högsta toppen är högst dubbelt så stor som höjden på den lägsta. Dvärgen kan välja ordningen på topparna godtyckligt. Hans mål är att minimera den totala minskningen av medieintresseenheter under hela expeditionen.

Kan du hjälpa honom att välja i vilken ordning han ska besöka alla toppar så att minskningen av medieintresseenheter minimeras?

Indata

Den första raden i indatan innehåller talet $T$, som anger antalet testfall.

Den första raden i varje testfall innehåller ett enda heltal $N$, som anger antalet toppar som ska besökas av Resenären.

Den andra raden i testfallet innehåller $N$ heltal $a_1, \dots, a_N$, som uppfyller villkoren i problemet.

Utdata

För varje testfall, skriv ut två rader. Den första raden ska innehålla ett enda heltal som anger den minsta möjliga minskningen i medieintresseenheter för dvärgens resa.

Den andra raden ska innehålla höjderna $a_1, \dots, a_N$ ordnade i den följd som Dvärgen bör besöka dem för att uppnå denna minimala minskning.

Om det finns flera optimala lösningar kan du skriva ut vilken som helst av dem.

Begränsningar

$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\}$, summan av värdena på $N$ i indatan överstiger inte $10^6$.

Exempel

Indata 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