Alice dan Bob memiliki $2n$ kartu, masing-masing bertuliskan sebuah bilangan bulat, sedemikian sehingga setiap bilangan bulat antara $1$ dan $n$ muncul pada tepat dua kartu. Pada awalnya, Alice dan Bob masing-masing memegang $n$ kartu.

Mereka akan memainkan permainan kartu, dengan Alice melangkah lebih dulu. Pada setiap giliran, pemain saat ini meletakkan sebuah kartu dari tangannya ke bagian atas tumpukan. Jika sekarang terdapat dua kartu dengan angka yang sama di dalam tumpukan, pemain saat ini mendapatkan $1$ poin dan mengambil kedua kartu yang cocok tersebut beserta semua kartu di antaranya, lalu meletakkannya ke tumpukan buangan.

Diberikan urutan langkah Alice, bagaimana Bob dapat mengatur langkahnya untuk meminimalkan skor Alice?

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 5 \times 10^5$).

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), yang menyatakan angka pada kartu yang dimainkan oleh Alice secara berurutan. Dijamin bahwa tidak ada angka yang muncul lebih dari dua kali di dalam $a_i$.

Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $5 \times 10^5$.

Keluaran

Untuk setiap kasus uji, baris pertama keluaran harus berisi sebuah bilangan bulat, yang menyatakan skor minimum yang dapat diperoleh Alice.

Baris kedua harus berisi $n$ bilangan bulat $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), yang menyatakan langkah Bob secara berurutan, sedemikian sehingga setiap bilangan bulat dari $1$ hingga $n$ muncul tepat dua kali dalam gabungan barisan $a_i$ dan $b_i$.

Contoh

Masukan

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

Keluaran

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

Catatan

Untuk kasus uji ketiga, permainan berlangsung sebagai berikut: