Alice og Bob har $2n$ kort, hvert med et heltall skrevet på seg, slik at hvert heltall mellom $1$ og $n$ forekommer på nøyaktig to kort. Til å begynne med har Alice og Bob $n$ kort hver.

De skal spille et kortspill, der Alice begynner. I hvert trekk legger den aktuelle spilleren et kort fra hånden sin øverst i bunken. Hvis det nå er to kort med samme tall i bunken, får den aktuelle spilleren $1$ poeng og fjerner de to matchende kortene sammen med alle kortene imellom, og legger dem i kastebunken.

Gitt Alices sekvens av trekk, hvordan kan Bob ordne trekkene sine for å minimere Alices poengsum?

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^5$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($1 \le n \le 5 \times 10^5$).

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), som representerer tallene på kortene som spilles av Alice i rekkefølge. Det garanteres at ingen tall forekommer mer enn to ganger i $a_i$.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $5 \times 10^5$.

Utdata

For hvert testtilfelle skal den første linjen i utdata inneholde et heltall, som representerer den minste poengsummen Alice kan få.

Den andre linjen skal inneholde $n$ heltall $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), som representerer Bobs trekk i rekkefølge, slik at hvert heltall fra $1$ til $n$ forekommer nøyaktig to ganger i de kombinerte sekvensene av $a_i$ og $b_i$.

Eksempel

Inndata

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

Utdata

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

Forklaring

For det tredje testtilfellet foregår spillet som følger: