Kurcaci Sang Pengembara telah memutuskan untuk memfokuskan perhatiannya tahun ini pada penaklukan puncak-puncak di Wroclaw. Tujuan terbarunya adalah menaklukkan $N$ puncak berbeda selama $N$ hari berturut-turut, tepat satu puncak setiap harinya. Menaklukkan puncak adalah hal yang sangat mudah bagi Sang Pengembara. Ia dapat menaklukkan puncak mana pun pada hari apa pun, sehingga ia memutuskan untuk membuat seluruh ekspedisi ini mendapatkan publisitas sebaik mungkin di media.

Kurcaci tersebut baru-baru ini menyadari suatu pola tertentu:

• Setelah menaklukkan puncak pertama, minat media akan tinggi, berapa pun ketinggiannya.
• Jika pada suatu hari ia menaklukkan puncak dengan ketinggian $a$, dan pada hari berikutnya puncak dengan ketinggian $b$, maka minat media terhadap ekspedisinya berkurang sebesar $\lfloor a/b \rfloor$ satuan, yang ia sebut sebagai satuan minat media.

Sang Pengembara sudah tahu bahwa ia harus menaklukkan $N$ puncak dengan ketinggian $a_1, \dots, a_N$. Selain itu, ternyata ketinggian puncak tertinggi paling banyak dua kali lipat ketinggian puncak terendah. Sang kurcaci dapat memilih urutan puncak secara bebas. Tujuannya adalah meminimalkan total penurunan satuan minat media selama seluruh ekspedisi berlangsung.

Dapatkah Anda membantunya memilih urutan untuk mengunjungi semua puncak sehingga penurunan satuan minat media menjadi seminimal mungkin?

Masukan

Baris pertama masukan berisi bilangan $T$, yang menyatakan banyaknya kasus uji.

Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $N$, yang menyatakan banyaknya puncak yang akan dikunjungi oleh Sang Pengembara.

Baris kedua dari kasus uji berisi $N$ bilangan bulat $a_1, \dots, a_N$, yang memenuhi syarat-syarat yang disebutkan dalam soal.

Keluaran

Untuk setiap kasus uji, keluarkan dua baris. Baris pertama harus berisi sebuah bilangan bulat yang menyatakan penurunan minimum yang mungkin dari satuan minat media untuk perjalanan sang kurcaci.

Baris kedua harus berisi ketinggian $a_1, \dots, a_N$ yang disusun sesuai urutan kunjungan Sang Kurcaci untuk mencapai penurunan minimum tersebut.

Jika terdapat beberapa solusi optimal, Anda boleh mengeluarkan yang mana saja.

Batasan

$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\}$, jumlah nilai $N$ yang diberikan dalam masukan tidak melebihi $10^6$.

Contoh

Masukan 1

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

Keluaran 1

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