Гном-Мандрівник вирішив цього року зосередити свою увагу на підкоренні вершин Вроцлава. Його найновіша мета — підкорити $N$ різних вершин за $N$ послідовних днів, рівно по одній вершині щодня. Підкорення вершин для Мандрівника — завиграшки. Він може підкорити будь-яку вершину в будь-який день, тому він вирішив зробити всю експедицію якомога ширше висвітленою в медіа.

Нещодавно гном помітив певну закономірність:

• Після підкорення першої вершини інтерес медіа буде високим незалежно від її висоти.
• Якщо одного дня він підкорює вершину висоти $a$, а наступного дня — вершину висоти $b$, то інтерес медіа до його експедиції зменшується на $\lfloor a/b \rfloor$ одиниць, які він називає одиницями медійного інтересу.

Мандрівник уже знає, що йому доведеться підкорити $N$ вершин із висотами $a_1, \dots, a_N$. Крім того, виявляється, що висота найвищої вершини щонайбільше вдвічі перевищує висоту найнижчої. Гном може обрати порядок вершин довільно. Його мета — мінімізувати сумарне зменшення одиниць медійного інтересу протягом усієї експедиції.

Чи можете ви допомогти йому обрати порядок відвідування всіх вершин так, щоб зменшення одиниць медійного інтересу було мінімальним?

Вхідні дані

Перший рядок вхідних даних містить число $T$, що позначає кількість тестових випадків.

Перший рядок кожного тестового випадку містить одне ціле число $N$, що позначає кількість вершин, які має відвідати Мандрівник.

Другий рядок тестового випадку містить $N$ цілих чисел $a_1, \dots, a_N$, які задовольняють умови задачі.

Вихідні дані

Для кожного тестового випадку виведіть два рядки. Перший рядок повинен містити одне ціле число, що позначає мінімально можливе зменшення одиниць медійного інтересу для подорожі гнома.

Другий рядок повинен містити висоти $a_1, \dots, a_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\}$, сума значень $N$ у вхідних даних не перевищує $10^6$.

Приклади

Вхідні дані 1

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

Вихідні дані 1

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