Alice と Bob は $2n$ 枚のカードを持っています。各カードには整数が書かれており、$1$ から $n$ までの各整数はちょうど 2 枚のカードに書かれています。最初、Alice と Bob はそれぞれ $n$ 枚のカードを手札として持っています。

二人は Alice の先手でカードゲームを行います。各手番では、手番のプレイヤーが手札からカードを 1 枚選び、場の山の一番上に置きます。このとき、場の山に同じ数が書かれたカードが 2 枚存在するならば、手番のプレイヤーは $1$ 点を獲得し、その 2 枚のカードとそれらの間にあるすべてのカードを場の山から取り除いて捨て札置き場に置きます。

Alice が場に出すカードの順序が与えられたとき、Bob は Alice の得点を最小化するために自分の出すカードの順序をどのように決めればよいでしょうか？

入力

最初の行には、テストケースの数を表す整数 $T$ ($1 \le T \le 10^5$) が与えられます。

各テストケースについて、最初の行には整数 $n$ ($1 \le n \le 5 \times 10^5$) が与えられます。

2 行目には、Alice が順番に出すカードに書かれた数を表す $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が与えられます。どの数も $a_i$ の中に 3 回以上現れないことが保証されます。

すべてのテストケースにおける $n$ の総和は $5 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、1 行目には Alice が獲得する得点の最小値を表す整数を出力してください。

2 行目には、Bob が順番に出すカードを表す $n$ 個の整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) を出力してください。ただし、$1$ から $n$ までの各整数は、$a_i$ と $b_i$ を合わせた列の中でちょうど 2 回ずつ現れなければなりません。

入出力例

入力

3
3
1 2 3
5
3 1 4 1 5
5
1 4 5 1 4

出力

0
1 2 3
0
2 3 2 4 5
1
3 2 2 3 5

ノート

3 番目のテストケースでは、ゲームは次のように進行します：