Chú lùn Lữ khách đã quyết định tập trung sự chú ý của mình trong năm nay vào việc chinh phục các đỉnh núi ở Wroclaw. Mục tiêu mới nhất của anh là chinh phục $N$ đỉnh núi khác nhau trong $N$ ngày liên tiếp, mỗi ngày đúng một đỉnh núi. Việc chinh phục các đỉnh núi dễ như ăn kẹo đối với Lữ khách. Anh có thể chinh phục bất kỳ đỉnh núi nào vào bất kỳ ngày nào, vì vậy anh quyết định làm cho toàn bộ cuộc thám hiểm được truyền thông chú ý nhiều nhất có thể.

Gần đây chú lùn đã nhận ra một quy luật nhất định:

• Sau khi chinh phục đỉnh núi đầu tiên, sự quan tâm của truyền thông sẽ ở mức cao, bất kể độ cao của nó.
• Nếu vào một ngày anh chinh phục một đỉnh núi có độ cao $a$, và vào ngày hôm sau chinh phục một đỉnh núi có độ cao $b$, sự quan tâm của truyền thông đối với cuộc thám hiểm của anh sẽ giảm đi $\lfloor a/b \rfloor$ đơn vị, mà anh gọi là đơn vị quan tâm truyền thông.

Lữ khách đã biết mình sẽ phải chinh phục $N$ đỉnh núi có độ cao $a_1, \dots, a_N$. Ngoài ra, hóa ra độ cao của đỉnh núi cao nhất không vượt quá hai lần độ cao của đỉnh núi thấp nhất. Chú lùn có thể tùy ý chọn thứ tự các đỉnh núi. Mục tiêu của anh là cực tiểu hóa tổng lượng giảm đơn vị quan tâm truyền thông trong suốt toàn bộ cuộc thám hiểm.

Bạn có thể giúp anh ấy chọn thứ tự ghé thăm tất cả các đỉnh núi sao cho lượng giảm đơn vị quan tâm truyền thông là nhỏ nhất không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số $T$, biểu thị số lượng bộ test.

Dòng đầu tiên của mỗi bộ test chứa một số nguyên $N$, biểu thị số lượng đỉnh núi mà Lữ khách sẽ ghé thăm.

Dòng thứ hai của bộ test chứa $N$ số nguyên $a_1, \dots, a_N$, thỏa mãn các điều kiện nêu trong đề bài.

Dữ liệu ra

Với mỗi bộ test, in ra hai dòng. Dòng đầu tiên chứa một số nguyên duy nhất biểu thị lượng giảm đơn vị quan tâm truyền thông nhỏ nhất có thể cho hành trình của chú lùn.

Dòng thứ hai chứa các độ cao $a_1, \dots, a_N$ được sắp xếp theo thứ tự mà Chú lùn nên ghé thăm để đạt được lượng giảm nhỏ nhất này.

Nếu có nhiều lời giải tối ưu, bạn có thể in ra bất kỳ lời giải nào.

Giới hạn

$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\}$, tổng các giá trị của $N$ trong dữ liệu vào không vượt quá $10^6$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

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