Le nain Voyageur a décidé de concentrer son attention cette année sur la conquête des sommets de Wroclaw. Son dernier objectif est de conquérir $N$ sommets différents sur $N$ jours consécutifs, à raison d'exactement un sommet par jour. Conquérir des sommets est un jeu d'enfant pour le Voyageur. Il peut conquérir n'importe quel sommet n'importe quel jour, c'est pourquoi il a décidé de rendre toute l'expédition aussi médiatisée que possible.

Le nain a récemment remarqué un certain phénomène :

• Après avoir conquis le premier sommet, l'intérêt des médias sera élevé, quelle que soit sa hauteur.
• Si un jour il conquiert un sommet de hauteur $a$, et le lendemain un sommet de hauteur $b$, l'intérêt des médias pour son expédition diminue de $\lfloor a/b \rfloor$ unités, qu'il appelle unités d'intérêt médiatique.

Le Voyageur sait déjà qu'il devra conquérir $N$ sommets de hauteurs $a_1, \dots, a_N$. De plus, il s'avère que la hauteur du sommet le plus élevé est au plus égale au double de la hauteur du plus bas. Le nain peut choisir l'ordre des sommets arbitrairement. Son objectif est de minimiser la diminution totale en unités d'intérêt médiatique tout au long de l'expédition.

Pouvez-vous l'aider à choisir l'ordre de visite de tous les sommets afin que la diminution en unités d'intérêt médiatique soit minimisée ?

Entrée

La première ligne d'entrée contient le nombre $T$, représentant le nombre de cas de test.

La première ligne de chaque cas de test contient un seul entier $N$, représentant le nombre de sommets devant être visités par le Voyageur.

La deuxième ligne du cas de test contient $N$ entiers $a_1, \dots, a_N$, satisfaisant aux conditions énoncées dans le problème.

Sortie

Pour chaque cas de test, affichez deux lignes. La première ligne doit contenir un seul entier représentant la diminution minimale possible en unités d'intérêt médiatique pour le périple du nain.

La deuxième ligne doit contenir les hauteurs $a_1, \dots, a_N$ disposées dans l'ordre dans lequel le nain doit les visiter pour atteindre cette diminution minimale.

S'il existe plusieurs solutions optimales, vous pouvez afficher n'importe laquelle d'entre elles.

Limites

$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 somme des valeurs de $N$ fournies dans l'entrée ne dépasse pas $10^6$.

Exemples

Entrée 1

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

Sortie 1

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