Ferðalangsdvergurinn hefur ákveðið að beina athygli sinni í ár að því að sigra tinda Wrocław. Nýjasta markmið hans er að sigra $N$ ólíka tinda á $N$ samfelldum dögum, nákvæmlega einn tind á hverjum degi. Að sigra tinda er leikur einn fyrir Ferðalanginn. Hann getur sigrað hvaða tind sem er á hvaða degi sem er, og því hefur hann ákveðið að gera allan leiðangurinn eins áberandi í fjölmiðlum og mögulegt er.

Dvergurinn hefur nýlega tekið eftir ákveðnu mynstri:

• Eftir að fyrsti tindurinn hefur verið sigraður verður áhugi fjölmiðla mikill, óháð hæð hans.
• Ef hann sigrar tind af hæð $a$ einn daginn, og tind af hæð $b$ næsta dag, minnkar áhugi fjölmiðla á leiðangri hans um $\lfloor a/b \rfloor$ einingar, sem hann kallar fjölmiðlaáhugaeiningar.

Ferðalangurinn veit nú þegar að hann mun þurfa að sigra $N$ tinda með hæðirnar $a_1, \dots, a_N$. Að auki kemur í ljós að hæð hæsta tindsins er í mesta lagi tvöföld hæð þess lægsta. Dvergurinn getur valið röð tindanna að vild. Markmið hans er að lágmarka heildarminnkun fjölmiðlaáhugaeininga í öllum leiðangrinum.

Geturðu hjálpað honum að velja í hvaða röð hann á að heimsækja alla tindana þannig að minnkunin á fjölmiðlaáhugaeiningum verði sem minnst?

Inntak

Fyrsta lína inntaksins inniheldur töluna $T$, sem táknar fjölda prófunartilvika.

Fyrsta línan í hverju prófunartilviki inniheldur eina heiltölu $N$, sem táknar fjölda tinda sem Ferðalangurinn mun heimsækja.

Önnur línan í prófunartilvikinu inniheldur $N$ heiltölur $a_1, \dots, a_N$, sem uppfylla skilyrðin sem fram koma í dæminu.

Úttak

Fyrir hvert prófunartilvik skaltu prenta tvær línur. Fyrri línan á að innihalda eina heiltölu sem táknar minnstu mögulegu minnkun á fjölmiðlaáhugaeiningum í ferðalagi dvergsins.

Seinni línan á að innihalda hæðirnar $a_1, \dots, a_N$ í þeirri röð sem Dvergurinn ætti að heimsækja þær til að ná þessari lágmarksminnkun.

Ef til eru margar bestu lausnir máttu prenta hverja sem er þeirra.

Takmarkanir

$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\}$, summa gilda $N$ sem gefin eru í inntakinu fer ekki yfir $10^6$.

Dæmi

Inntak 1

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

Úttak 1

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