Alice e Bob hanno $2n$ carte, ciascuna con un intero scritto sopra, in modo tale che ogni intero compreso tra $1$ e $n$ compaia esattamente su due carte. Inizialmente, Alice e Bob tengono in mano $n$ carte ciascuno.

Stanno per giocare a un gioco di carte, in cui Alice inizia per prima. Ad ogni turno, il giocatore di turno posiziona una carta dalla propria mano in cima alla pila. Se ora ci sono due carte con lo stesso numero nella pila, il giocatore di turno ottiene $1$ punto e rimuove le due carte corrispondenti insieme a tutte le carte comprese tra di esse, mettendole nella pila degli scarti.

Data la sequenza di mosse di Alice, come può Bob organizzare le sue mosse per minimizzare il punteggio di Alice?

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^5$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene un intero $n$ ($1 \le n \le 5 \times 10^5$).

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), che rappresentano nell'ordine i numeri sulle carte giocate da Alice. È garantito che nessun numero compaia più di due volte in $a_i$.

È garantito che la somma di $n$ su tutti i casi di test non supera $5 \times 10^5$.

Output

Per ogni caso di test, la prima riga di output deve contenere un intero, che rappresenta il punteggio minimo che Alice può ottenere.

La seconda riga deve contenere $n$ interi $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), che rappresentano nell'ordine le mosse di Bob, in modo tale che ogni intero da $1$ a $n$ compaia esattamente due volte nelle sequenze combinate di $a_i$ e $b_i$.

Esempio

Input

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

Output

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

Nota

Per il terzo caso di test, il gioco procede come segue: