Гном-Путешественник решил в этом году сосредоточить своё внимание на покорении вершин Вроцлава. Его новейшая цель — покорить $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