Alice i Bob mają $2n$ kart, na każdej z nich napisana jest liczba całkowita w taki sposób, że każda liczba całkowita od $1$ do $n$ występuje dokładnie na dwóch kartach. Początkowo Alice i Bob trzymają w ręku po $n$ kart.

Zamierzają zagrać w grę karcianą, w której zaczyna Alice. W każdej turze aktualny gracz kładzie kartę ze swojej ręki na wierzchu stosu. Jeśli na stosie znajdują się teraz dwie karty z tą samą liczbą, aktualny gracz zdobywa $1$ punkt i zdejmuje dwie pasujące karty wraz ze wszystkimi kartami znajdującymi się pomiędzy nimi, odkładając je na stos kart odrzuconych.

Znając ciąg ruchów Alice, w jaki sposób Bob może zaplanować swoje ruchy, aby zminimalizować wynik Alice?

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^5$).

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), reprezentujących kolejno liczby na kartach zagrywanych przez Alice. Gwarantowane jest, że żadna liczba nie występuje w $a_i$ więcej niż dwa razy.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego przypadku testowego pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą minimalny wynik, jaki może uzyskać Alice.

Drugi wiersz powinien zawierać $n$ liczb całkowitych $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), reprezentujących kolejne ruchy Boba, tak aby każda liczba całkowita od $1$ do $n$ występowała dokładnie dwa razy w połączonych ciągach $a_i$ oraz $b_i$.

Przykład

Wejście

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

Wyjście

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

Uwaga

Dla trzeciego przypadku testowego gra przebiega następująco: