旅人ドワーフは今年、ヴロツワフの峰々を制覇することに注力すると決めました。彼の最新の目標は、連続する $N$ 日間で $N$ 個の異なる峰を、1 日につきちょうど 1 つずつ制覇することです。旅人にとって峰の制覇など朝飯前であり、どの日にどの峰でも制覇することができます。そこで彼は、遠征全体がメディアで可能な限り大きく取り上げられるようにすることにしました。

ドワーフは最近、ある法則に気づきました：

• 最初の峰を制覇した後は、その高さにかかわらずメディアの関心は高い。
• ある日に高さ $a$ の峰を制覇し、その翌日に高さ $b$ の峰を制覇すると、彼の遠征に対するメディアの関心は $\lfloor a/b \rfloor$ 単位だけ減少する。彼はこれをメディア関心単位と呼んでいる。

旅人はすでに、自分が制覇しなければならない $N$ 個の峰の高さが $a_1, \dots, a_N$ であることを知っています。さらに、最も高い峰の高さは、最も低い峰の高さの高々 2 倍であることが分かっています。ドワーフは峰を訪れる順序を自由に選ぶことができます。彼の目標は、遠征全体におけるメディア関心単位の合計減少量を最小化することです。

メディア関心単位の減少量が最小になるように、すべての峰を訪れる順序を選ぶのを手伝ってあげられますか？

入力

入力の 1 行目には、テストケースの個数を表す整数 $T$ が与えられます。

各テストケースの 1 行目には、旅人が訪れる峰の個数を表す 1 つの整数 $N$ が与えられます。

テストケースの 2 行目には、問題文の条件を満たす $N$ 個の整数 $a_1, \dots, a_N$ が与えられます。

出力

各テストケースについて、2 行を出力してください。1 行目には、ドワーフの旅におけるメディア関心単位の減少量の最小値を表す 1 つの整数を出力してください。

2 行目には、この最小の減少量を達成するためにドワーフが訪れるべき順序に並べた高さ $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