El enano Viajero ha decidido centrar su atención este año en conquistar las cumbres de Breslavia. Su último objetivo es conquistar $N$ cumbres diferentes durante $N$ días consecutivos, exactamente una cumbre cada día. Conquistar cumbres es pan comido para el Viajero. Puede conquistar cualquier cumbre en cualquier día, por lo que ha decidido hacer que toda la expedición tenga la mayor repercusión posible en los medios de comunicación.

El enano ha notado recientemente cierto patrón:

• Después de conquistar la primera cumbre, el interés de los medios será alto, independientemente de su altura.
• Si en un día conquista una cumbre de altura $a$, y al día siguiente una cumbre de altura $b$, el interés de los medios en su expedición disminuye en $\lfloor a/b \rfloor$ unidades, a las que él llama unidades de interés mediático.

El Viajero ya sabe que tendrá que conquistar $N$ cumbres con alturas $a_1, \dots, a_N$. Además, resulta que la altura de la cumbre más alta es a lo sumo el doble de la altura de la más baja. El enano puede elegir el orden de las cumbres arbitrariamente. Su objetivo es minimizar la disminución total en unidades de interés mediático durante toda la expedición.

¿Puedes ayudarle a elegir el orden para visitar todas las cumbres de modo que se minimice la disminución en unidades de interés mediático?

Entrada

La primera línea de entrada contiene el número $T$, que representa el número de casos de prueba.

La primera línea de cada caso de prueba contiene un solo entero $N$, que representa el número de cumbres que visitará el Viajero.

La segunda línea del caso de prueba contiene $N$ enteros $a_1, \dots, a_N$, que satisfacen las condiciones indicadas en el problema.

Salida

Para cada caso de prueba, imprime dos líneas. La primera línea debe contener un solo entero que represente la mínima disminución posible en unidades de interés mediático para el viaje del enano.

La segunda línea debe contener las alturas $a_1, \dots, a_N$ dispuestas en el orden en que el enano debe visitarlas para lograr esta disminución mínima.

Si existen múltiples soluciones óptimas, puedes imprimir cualquiera de ellas.

Límites

$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\}$, la suma de los valores de $N$ proporcionados en la entrada no supera $10^6$.

Ejemplos

Entrada 1

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

Salida 1

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