Matkaajakääpiö on päättänyt keskittää tänä vuonna huomionsa Wrocławin huippujen valloittamiseen. Hänen uusin tavoitteensa on valloittaa $N$ eri huippua $N$ peräkkäisenä päivänä, täsmälleen yksi huippu päivässä. Huippujen valloittaminen on Matkaajalle lastenleikkiä. Hän voi valloittaa minkä tahansa huipun minä tahansa päivänä, ja siksi hän on päättänyt tehdä koko retkikunnasta mahdollisimman näkyvän mediassa.

Kääpiö on hiljattain huomannut tietyn säännönmukaisuuden:

• Ensimmäisen huipun valloittamisen jälkeen median kiinnostus on korkealla huipun korkeudesta riippumatta.
• Jos hän yhtenä päivänä valloittaa huipun, jonka korkeus on $a$, ja seuraavana päivänä huipun, jonka korkeus on $b$, median kiinnostus hänen retkikuntaansa kohtaan vähenee $\lfloor a/b \rfloor$ yksikköä, joita hän kutsuu median kiinnostusyksiköiksi.

Matkaaja tietää jo, että hänen on valloitettava $N$ huippua, joiden korkeudet ovat $a_1, \dots, a_N$. Lisäksi käy ilmi, että korkeimman huipun korkeus on enintään kaksinkertainen matalimman huipun korkeuteen verrattuna. Kääpiö voi valita huippujen järjestyksen mielivaltaisesti. Hänen tavoitteenaan on minimoida median kiinnostusyksiköiden kokonaisvähenemä koko retkikunnan aikana.

Voitko auttaa häntä valitsemaan kaikkien huippujen vierailujärjestyksen siten, että median kiinnostusyksiköiden vähenemä on mahdollisimman pieni?

Syöte

Syötteen ensimmäinen rivi sisältää luvun $T$, joka ilmaisee testitapausten lukumäärän.

Kunkin testitapauksen ensimmäinen rivi sisältää yhden kokonaisluvun $N$, joka ilmaisee Matkaajan vierailemien huippujen lukumäärän.

Testitapauksen toinen rivi sisältää $N$ kokonaislukua $a_1, \dots, a_N$, jotka toteuttavat tehtävässä esitetyt ehdot.

Tuloste

Tulosta jokaiselle testitapaukselle kaksi riviä. Ensimmäisen rivin tulee sisältää yksi kokonaisluku, joka ilmaisee pienimmän mahdollisen median kiinnostusyksiköiden vähenemän kääpiön matkalla.

Toisen rivin tulee sisältää korkeudet $a_1, \dots, a_N$ järjestettyinä siihen järjestykseen, jossa Kääpiön tulisi vierailla niillä saavuttaakseen tämän pienimmän vähenemän.

Jos optimaalisia ratkaisuja on useita, voit tulostaa niistä minkä tahansa.

Rajoitukset

$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\}$, syötteessä annettujen luvun $N$ arvojen summa on enintään $10^6$.

Esimerkit

Syöte 1

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

Tuloste 1

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